如果这篇博客帮助到你，可以请我喝一杯咖啡~
CC BY 4.0 （除特别声明或转载文章外）
Coord getCoord()
{
lf x,y;
return scanf("%lf%lf",&x,&y),Coord(x,y);
}
基础题目
Triangle Fun
按照题目意思的直接解法。
int main()
{
int n;
for(scanf("%d",&n); n--;)
{
Coord A=getCoord(),B=getCoord(),C=getCoord(),
D=B+(C-B)/3.0,E=C+(A-C)/3.0,F=A+(B-A)/3.0,
P=getLineIntersection(A,D,B,E),
Q=getLineIntersection(B,E,C,F),
R=getLineIntersection(C,F,A,D);
printf("%.0f\n",fabs(Area2(P,Q,R)/2));
}
}
可证明$\triangle ABC$的面积是$\triangle PQR$的 7 倍，于是有下面的解法。
int main()
{
int n;
for(scanf("%d",&n);
n--;
printf("%.0f\n",
fabs(Area2(getCoord(),getCoord(),getCoord())/14)));
}
Determine the Shape
int main()
{
char s[6][32]=
{
"Square",
"Rectangle",
"Rhombus",
"Parallelogram",
"Trapezium",
"Ordinary Quadrilateral"
};
int t,kase=0,ans;
for(scanf("%d",&t); t--; printf("Case %d: %s\n",++kase,s[ans]))
{
ans=5;
Coord p[4]= {getCoord(),getCoord(),getCoord(),getCoord()};
sort(p,p+4,cmpCoord);
do
{
Coord &a=p[0],&b=p[1],&c=p[2],&d=p[3];
if(!sgn(Cross(b-a,d-c))||!sgn(Cross(a-d,c-b)))ans=min(ans,4);
if(!sgn(Cross(b-a,d-c))&&!sgn(Cross(a-d,c-b)))
{
ans=min(ans,sgn(Dot(c-a,b-d))?3:2);
if(!sgn(Dot(b-a,c-b)))
ans=min(ans,sgn(Dot(c-a,b-d))?1:0);
}
}
while(next_permutation(p,p+4,cmpCoord));
}
}
Athletics Track
int main()
{
for(lf a,b,c,kase=0;
~scanf("%lf : %lf",&a,&b);
printf("Case %.0f: %.5f %.5f\n",kase+=1,a*c,b*c))
c=200/(sqrt(a*a+b*b)*atan(b/a)+a);
}
Tunnelling the Earth
int main()
{
int n;
Sphere earth(Coord3(0,0,0),6371009);
for(scanf("%d",&n); n--;)
{
lf a,b,c,d;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
Coord3 A(earth.point(a,b)),B(earth.point(c,d));
printf("%.0f\n",fabs(Angle(A,B)*earth.r)-abs(A-B));
}
}
二维几何计算
Morley’s Theorem
int main()
{
int t;
for(scanf("%d",&t); t--; printf("\n"))
{
Coord A=getCoord(),B=getCoord(),C=getCoord(),D;
for(int i=0; i!=3; ++i)
{
lf b=Angle(A-B,C-B),c=Angle(A-C,B-C);
Line BD(B,Rotate(C-B,b/3)),CD(C,Rotate(B-C,-c/3));
D=getLineIntersection(BD,CD);
printf("%.6f %.6f ",D.X,D.Y);
swap(A,B),swap(B,C);
}
}
}
That Nice Euler Circuit
struct CoordCmp
{
bool operator()(Coord A,Coord B)
{
return cmpCoord(A,B);
}
};
int main()
{
for(int e,kase=0; scanf("%d",&e)&&e; printf("Case %d: There are %d pieces.\n",++kase,--e))//读入时e本身大1个（最后一笔回到起点），因此上面得到的边数要减去一个
{
vector<Coord> p;
set<Coord,CoordCmp> v;
for(int i=0; i<e; ++i)
{
p.push_back(getCoord());
v.insert(p.back());
for(int j=1; j<i; ++j)
if(SegmentProperIntersection(p[i-1],p[i],p[j-1],p[j]))//不包含端点的相交
v.insert(getLineIntersection(p[i-1],p[i],p[j-1],p[j]));
}
for(set<Coord,CoordCmp>::iterator i=v.begin(); i!=v.end(); ++i)
for(int j=1; j<p.size(); ++j)
if(onSegment(*i,p[j-1],p[j]))
++e;
e+=2-v.size();//欧拉定理：平面图的点数V、边数E和面数F满足F=E+2-V
}
}
Dog Distance
int main()
{
int I,kase=0,a[2];
lf maxd,mind,t,len[2];
Coord p[2];
vector<Coord> q[2];
for(scanf("%d",&I); I--; printf("Case %d: %.0f\n",++kase,maxd-mind))
{
scanf("%d%d",&a[0],&a[1]);
for(int i=0; i<2; ++i)
{
while(a[i]--)q[i].push_back(getCoord());
for(int j=len[i]=0; j+1<q[i].size(); ++j)
len[i]+=abs(q[i][j]-q[i][j+1]);
p[i]=q[i].back(),q[i].pop_back();
}
for(maxd=mind=abs(p[0]-p[1]); !q[0].empty()&&!q[1].empty();)
{
Coord v[2]= {q[0].back()-p[0],q[1].back()-p[1]};
t=min(abs(v[0])/len[0],abs(v[1])/len[1]);
for(int i=0; i<2; ++i)
if(q[i].back()==(p[i]+=v[i]*=t*len[i]/abs(v[i])))
q[i].pop_back();
maxd=max(maxd,abs(p[0]-p[1]));
mind=min(mind,DistanceToSegment(p[0],p[1]-v[1]+v[0],p[1]));
}
}
}
2D Geometry 110 in 1!
EPS 调成 1e-6，再小判定圆和直线相切受影响。
lf getlf()
{
lf x;
return scanf("%lf",&x),x;
}
Coord getCoord()
{
lf x=getlf(),y=getlf();
return Coord(x,y);
}
void printf(lf sol)
{
printf("%.6lf",sol);
}
void printf(Coord sol)
{
printf("("),printf(sol.X),printf(","),
printf(sol.Y),printf(")");
}
void printf(Circle sol)
{
printf("("),printf(sol.c.X),printf(","),
printf(sol.c.Y),printf(","),
printf(sol.r),printf(")");
}
template<typename T>
void printf(vector<T> sol)
{
sort(sol.begin(),sol.end(),cmpCoord);
printf("[");
for(int i=0; i!=sol.size(); ++i)
printf(i?",":""),printf(sol[i]);
printf("]");
}
int main()
{
for(char s[128]; ~scanf("%s",s); printf("\n"))
{
if(!strcmp(s,"CircumscribedCircle"))
{
Coord p[3]= {getCoord(),getCoord(),getCoord()},
p0=(p[1]+p[2])/2.0,
p2=(p[1]+p[0])/2.0;
Line l0(p0,Normal(p[2]-p[1])),
l2(p2,Normal(p[0]-p[1]));
Circle sol(getLineIntersection(l0,l2));
sol.r=abs(sol.c-p[1]);
printf(sol);
}
else if(!strcmp(s,"InscribedCircle"))
{
Coord p[3]= {getCoord(),getCoord(),getCoord()};
lf arg0=(arg(p[1]-p[0])+arg(p[2]-p[0]))/2,
arg2=(arg(p[1]-p[2])+arg(p[0]-p[2]))/2;
Line l0(p[0],polar(1.0,arg0)),
l2(p[2],polar(1.0,arg2));
Circle sol(getLineIntersection(l0,l2));
sol.r=fabs(DistanceToLine(sol.c,Line(p[0],p[2]-p[0])));
printf(sol);
}
else if(!strcmp(s,"TangentLineThroughPoint"))
{
Circle C(getCoord());
C.r=getlf();
Coord P=getCoord();
vector<Coord> ans;
getTangents(P,C,ans);
vector<lf> sol;
for(int i=0; i!=ans.size(); ++i)
{
sol.push_back(arg(ans[i]-P)*180/PI);
if(sol.back()<0)sol.back()+=180;
}
printf(sol);
}
else if(!strcmp(s,"CircleThroughAPointAndTangentToALineWithRadius"))
{
Circle C(getCoord());
Coord p[2]= {getCoord(),getCoord()};
C.r=getlf();
Coord mov=Normal(p[1]-p[0])*C.r;
Line L0(p[0]+mov,p[1]-p[0]),L1(p[0]-mov,p[1]-p[0]);
vector<Coord> sol;
getLineCircleIntersection(L0,C,sol);
getLineCircleIntersection(L1,C,sol);
printf(sol);
}
else if(!strcmp(s,"CircleTangentToTwoLinesWithRadius"))
{
Coord p[4]= {getCoord(),getCoord(),getCoord(),getCoord()};
lf r=getlf();
Coord mov=Normal(p[1]-p[0])*r;
Line L0(p[0]+mov,p[1]-p[0]),L1(p[0]-mov,p[1]-p[0]);
mov=Normal(p[3]-p[2])*r;
Line L2(p[2]+mov,p[3]-p[2]),L3(p[2]-mov,p[3]-p[2]);
vector<Coord> sol;
sol.push_back(getLineIntersection(L0,L2));
sol.push_back(getLineIntersection(L0,L3));
sol.push_back(getLineIntersection(L1,L2));
sol.push_back(getLineIntersection(L1,L3));
printf(sol);
}
else if(!strcmp(s,"CircleTangentToTwoDisjointCirclesWithRadius"))
{
Circle C[2];
for(int i=0; i!=2; ++i)
C[i].c=getCoord(),C[i].r=getlf();
lf r=getlf();
C[0].r+=r,C[1].r+=r;
vector<Coord> sol;
getCircleIntersection(C[0],C[1],sol);
printf(sol);
}
}
}
几何算法
Board Wrapping
凸包模板题。
int main()
{
int t,n;
for(scanf("%d",&t); t--;)
{
vector<Coord> p;
lf x,y,w,h,j,s=0;
for(scanf("%d",&n); n--; s+=w*h)
{
scanf("%lf%lf%lf%lf%lf",&x,&y,&w,&h,&j);
p.push_back(Coord(x,y)+Rotate(Coord(-w/2,-h/2),-j/180*PI));
p.push_back(Coord(x,y)+Rotate(Coord(w/2,-h/2),-j/180*PI));
p.push_back(Coord(x,y)+Rotate(Coord(-w/2,h/2),-j/180*PI));
p.push_back(Coord(x,y)+Rotate(Coord(w/2,h/2),-j/180*PI));
}
printf("%.1f %%\n",s*100/PolygonArea(ConvexHull(p)));
}
}
Airport
int main()
{
int t,n,kase=0;
for(scanf("%d",&t); t--;)
{
vector<Coord> p;
for(scanf("%d",&n); n--;)
{
lf x,y;
scanf("%lf%lf",&x,&y);
p.push_back(Coord(x,y));
}
if(p.size()<3)
{
printf("Case #%d: 0.000\n",++kase);
continue;
}
vector<Coord> ch(ConvexHull(p));
lf ans=INF;
for(int i=0; i<ch.size(); ++i)
{
lf sum=0,len=abs(ch[i]-ch[(i+1)%ch.size()]);
for(int j=0; j<p.size(); ++j)
sum+=Cross(ch[i]-p[j],ch[(i+1)%ch.size()]-p[j])/len;
ans=min(ans,sum);
}
printf("Case #%d: %.3f\n",++kase,ans/p.size());
}
}
The Great Divide
判断两凸包是否相交。
bool ConvexPolygonDisjoint(const vector<Coord> &ch1,const vector<Coord> &ch2)
{
for(int i=0; i<ch1.size(); ++i)
if(inPolygon(ch1[i],ch2))
return 0;
for(int i=0; i<ch2.size(); ++i)
if(inPolygon(ch2[i], ch1))
return 0;
for(int i=0; i<ch1.size(); ++i)
for(int j=0; j<ch2.size(); ++j)
if(SegmentProperIntersection(ch1[i],ch1[(i+1)%ch1.size()],ch2[j],ch2[(j+1)%ch2.size()]))
return 0;
return 1;
}
int main()
{
for(int n[2]; ~scanf("%d%d",&n[0],&n[1])&&n[0]&&n[1];)
{
vector<Coord> P[2];
for(int i=0; i<2; ++i)
for(int j=0; j<n[i]; ++j)
{
lf x,y;
scanf("%lf%lf",&x,&y);
P[i].push_back(Coord(x,y));
}
printf(ConvexPolygonDisjoint(ConvexHull(P[0]),ConvexHull(P[1]))?"Yes\n":"No\n");
}
}
Squares
int main()
{
int t,n;
for(scanf("%d",&t); t--;)
{
scanf("%d",&n);
vector<Coord> p;
for(int i=0; i<n; ++i)
{
lf x,y,w;
scanf("%lf%lf%lf",&x,&y,&w);
p.push_back(Coord(x,y));
p.push_back(Coord(x,y+w));
p.push_back(Coord(x+w,y));
p.push_back(Coord(x+w,y+w));
}
vector<Coord> ch(ConvexHull(p));
lf ans;
if(ch.size()==1)ans=0;
else if(ch.size()==2)ans=norm(ch[0]-ch[1]);
else
for(int u=ans=0,v=1,k; u<ch.size(); ++u)
for(;; v=(v+1)%ch.size())
if(k=sgn(Cross(ch[(u+1)%ch.size()]-ch[u],ch[(v+1)%ch.size()]-ch[v])),k<=0)
{
ans=max(ans,norm(ch[u]-ch[v]));
if(k==0)ans=max(ans,norm(ch[u]-ch[(v+1)%ch.size()]));
break;
}
printf("%.0f\n",ans);
}
}
Most Distant Point from the Sea
int main()
{
for(int n; ~scanf("%d", &n)&&n;)
{
lf l,r;
vector<Coord> p;
for(int i=0; i<n; ++i)
{
scanf("%lf%lf",&l,&r);
p.push_back(Coord(l,r));
}
for(l=0,r=INF; r-l>EPS;)
{
lf m=(l+r)/2;
vector<Line> L;
for(int i=0; i<n; ++i)
{
L.push_back(Line(p[i],p[(i+1)%n]-p[i]));
L.back().p+=m*Normal(L.back().v);
}
if(getHalfPlaneIntersection(L).empty())r=m;
else l=m;
}
printf("%.6f\n",l);
}
}