1.poj3335 Rotating Scoreboard
传送：http://poj.org/problem?id=3335
题意：就是有个球场，球场的形状是个凸多边形，然后观众是坐在多边形的边上的，问你是否在球场上有个地方可以放一个记分牌，然后所有的观众都可以看得到的。
分析：多边形是否存在内核。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cmath> 5 using namespace std; 6 const int maxn=110; 7 const double eps=1e-8; 8 int sgn(double x){ 9 if (fabs(x)<eps) return 0; 10 if (x<0) return -1; 11 return 1; 12 } 13 struct point{ 14 double x,y; 15 point(){} 16 point(double _x,double _y):x(_x),y(_y){} 17 point operator -(const point &b)const{ 18 return point(x-b.x,y-b.y); 19 } 20 double operator ^(const point &b)const{ 21 return x*b.y-y*b.x; 22 } 23 }p[maxn]; 24 struct line{ 25 point s,e; 26 line(){} 27 line(point _s,point _e):s(_s),e(_e){} 28 point crosspoint(line v){ 29 int a1=(v.e-v.s)^(s-v.s),a2=(v.e-v.s)^(e-v.s); 30 return point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1)); 31 } 32 //两向量平行（对应直线平行或重合） 33 bool parallel(line v){ 34 return sgn((e-s)^(v.e-v.s))==0; 35 } 36 }; 37 struct halfplane:public line{ 38 double angle; 39 halfplane(){} 40 halfplane(line v){s=v.s;e=v.e;} 41 void calcangle(){ 42 angle=atan2(e.y-s.y,e.x-s.x); 43 } 44 bool operator <(const halfplane &b)const{ 45 return angle<b.angle; 46 } 47 }; 48 struct halfplanes{ 49 int n; 50 halfplane hp[maxn]; 51 point p[maxn]; 52 int que[maxn]; int st,ed; //双端队列 53 void push(halfplane tmp){hp[n++]=tmp;} 54 //去重 55 void unique(){ 56 int m=1; 57 for (int i=1;i<n;i++){ 58 if (sgn(hp[i].angle-hp[i-1].angle)!=0) hp[m++]=hp[i]; 59 else if (sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0) hp[m-1]=hp[i]; 60 } 61 n=m; 62 } 63 bool halfplaneinsert(){ 64 for (int i=0;i<n;i++) hp[i].calcangle(); 65 sort(hp,hp+n); 66 unique(); 67 que[st=0]=0; que[ed=1]=1; 68 p[1]=hp[0].crosspoint(hp[1]); 69 for (int i=2;i<n;i++){ 70 while (st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0) ed--; 71 while (st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0) st++; 72 que[++ed]=i; 73 if (hp[i].parallel(hp[que[ed-1]])) return false; 74 p[ed]=hp[i].crosspoint(hp[que[ed-1]]); 75 } 76 while (st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0) ed--; 77 while (st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0) st++; 78 if (st+1>=ed) return false; else return true; 79 } 80 }; 81 halfplanes ha; 82 int main(){ 83 int t,n; cin >>t; 84 while (t--){ 85 cin >> n; 86 ha.n=0; 87 for (int i=0;i<n;i++) cin >> p[i].x >> p[i].y; 88 for (int i=0;i<n;i++){ 89 ha.push(halfplane(line(p[i],p[(i-1+n)%n]))); 90 } 91 if (ha.halfplaneinsert()) cout << "YES "; else cout << "NO "; 92 } 93 return 0; 94 }
2.poj1279 Art Gallery
传送：http://poj.org/problem?id=1279
题意：给一个多边形（顺时针给出点），求内核面积。
分析：rt。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 const int maxn=1505; 7 const double eps=1e-8; 8 int sgn(double x){ 9 if (fabs(x)<eps) return 0; 10 if (x<0) return -1; 11 return 1; 12 } 13 struct point{ 14 double x,y; 15 point(){} 16 point(double _x,double _y):x(_x),y(_y){} 17 point operator -(const point &b)const{ 18 return point(x-b.x,y-b.y); 19 } 20 double operator ^(const point &b)const{ 21 return x*b.y-y*b.x; 22 } 23 }p[maxn]; 24 struct line{ 25 point s,e; 26 line(){} 27 line(point _s,point _e):s(_s),e(_e){} 28 point crosspoint(line v){ 29 int a1=(v.e-v.s)^(s-v.s),a2=(v.e-v.s)^(e-v.s); 30 return point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1)); 31 } 32 //两向量平行（对应直线平行或重合） 33 bool parallel(line v){ 34 return sgn((e-s)^(v.e-v.s))==0; 35 } 36 }; 37 struct polygon{ 38 int n; 39 point p[maxn]; 40 double getarea(){ 41 double sum=0; 42 for (int i=0;i<n;i++) sum+=(p[i]^(p[(i+1)%n])); 43 return fabs(sum)/2; 44 } 45 }; 46 struct halfplane:public line{ 47 double angle; 48 halfplane(){} 49 halfplane(line v){s=v.s;e=v.e;} 50 void calcangle(){ 51 angle=atan2(e.y-s.y,e.x-s.x); 52 } 53 bool operator <(const halfplane &b)const{ 54 return angle<b.angle; 55 } 56 }; 57 polygon C; 58 struct halfplanes{ 59 int n; 60 halfplane hp[maxn]; 61 point p[maxn]; 62 int que[maxn]; int st,ed; //双端队列 63 void push(halfplane tmp){hp[n++]=tmp;} 64 //去重 65 void unique(){ 66 int m=1; 67 for (int i=1;i<n;i++){ 68 if (sgn(hp[i].angle-hp[i-1].angle)!=0) hp[m++]=hp[i]; 69 else if (sgn((hp[m-1].e-hp[m-1].s)^(hp[i].s-hp[m-1].s))>0) hp[m-1]=hp[i]; 70 } 71 n=m; 72 } 73 bool halfplaneinsert(){ 74 for (int i=0;i<n;i++) hp[i].calcangle(); 75 sort(hp,hp+n); 76 unique(); 77 que[st=0]=0; que[ed=1]=1; 78 p[1]=hp[0].crosspoint(hp[1]); 79 for (int i=2;i<n;i++){ 80 while (st<ed && sgn((hp[i].e-hp[i].s)^(p[ed]-hp[i].s))<0) ed--; 81 while (st<ed && sgn((hp[i].e-hp[i].s)^(p[st+1]-hp[i].s))<0) st++; 82 que[++ed]=i; 83 if (hp[i].parallel(hp[que[ed-1]])) return false; 84 p[ed]=hp[i].crosspoint(hp[que[ed-1]]); 85 } 86 while (st<ed && sgn((hp[que[st]].e-hp[que[st]].s)^(p[ed]-hp[que[st]].s))<0) ed--; 87 while (st<ed && sgn((hp[que[ed]].e-hp[que[ed]].s)^(p[st+1]-hp[que[ed]].s))<0) st++; 88 if (st+1>=ed) return false; else return true; 89 } 90 //得到最后半平面交的凸多边形 91 //得到先调用halfplaneinsert()，且返回true 92 void getconvex(polygon &con){ 93 p[st]=hp[que[st]].crosspoint(hp[que[ed]]); 94 con.n=ed-st+1; 95 for (int j=st,i=0;j<=ed;j++,i++) con.p[i]=p[j]; 96 } 97 }; 98 halfplanes ha; 99 int main(){ 100 int t,n; cin >> t; 101 while (t--){ 102 cin >> n; 103 for (int i=0;i<n;i++) cin >> p[i].x >> p[i].y; 104 ha.n=0; 105 for (int i=0;i<n;i++) ha.push(line(p[i],p[(i-1+n)%n])); 106 ha.halfplaneinsert(); 107 C.n=0; 108 ha.getconvex(C); 109 printf("%.2f ",C.getarea()); 110 } 111 return 0; 112 }
3.poj3525 Most Distant Point from the Sea
传送：http://poj.org/problem?id=3525
题意：给出一个海岛，求出岛上离海最远的点。输出距离。
分析：半平面交+二分。就是求多边形的最大半径圆 //板子
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 const double eps=1e-8; 7 const int maxn=110; 8 inline double sqr(double x){return x*x;} 9 int N; 10 int sgn(double x){ 11 if (fabs(x)<eps) return 0; 12 if (x<0) return -1; 13 return 1; 14 } 15 struct point{ 16 double x,y; 17 point(){} 18 point(double _x,double _y):x(_x),y(_y){} 19 point operator -(const point &b)const{ 20 return point(x-b.x,y-b.y); 21 } 22 double operator ^(const point &b)const{ 23 return x*b.y-y*b.x; 24 } 25 }; 26 struct line{ 27 point s,e; 28 double k; //斜率 29 line(){} 30 line(point _s,point _e):s(_s),e(_e){k=atan2(e.y-s.y,e.x-s.x);} 31 point operator &(const line &b)const{ //求两直线交点 32 point res=s; 33 double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e)); 34 res.x+=(e.x-s.x)*t; res.y+=(e.y-s.y)*t; 35 return res; 36 } 37 }; 38 point p[maxn]; //记录最初给的点集 39 line L[maxn]; //由最初的点集生成直线的集合 40 point pp[maxn]; //记录半平面交的结果的点集 41 //半平面交，直线的左边代表有效区域 42 bool HPIcmp(line a,line b){ //直线排序函数 43 if(sgn(a.k-b.k)!=0) return a.k<b.k; //斜率排序 44 //斜率相同我也不知道怎么办 45 return ((a.s-b.s)^(b.e-b.s))<0; 46 } 47 void HPI(line L[],int n,point res[],int &resn){ 48 //line是半平面交的直线的集合 n是直线的条数 res是结果 49 //的点集 resn是点集里面点的个数 50 int tot=n; 51 sort(L,L+n,HPIcmp); 52 tot=1; 53 //去掉斜率重复的 54 for(int i=1;i<n;i++) if(sgn(L[i].k-L[i-1].k)!=0) L[tot++]=L[i]; 55 int head,tail; line Q[maxn]; //双端队列 56 Q[head=0]=L[0]; Q[tail=1]=L[1]; 57 resn=0; 58 for(int i=2;i<tot;i++){ 59 if(sgn((Q[tail].e-Q[tail].s)^(Q[tail-1].e-Q[tail-1].s))==0|| 60 sgn((Q[head].e-Q[head].s)^(Q[head+1].e-Q[head+1].s))==0) return; 61 while(head<tail && (((Q[tail]&Q[tail-1])-L[i].s)^(L[i].e-L[i].s))>eps) tail--; 62 while(head<tail && (((Q[head]&Q[head+1])-L[i].s)^(L[i].e-L[i].s))>eps) head++; 63 Q[++tail]=L[i]; 64 } 65 while(head<tail && (((Q[tail]&Q[tail-1])-Q[head].s)^(Q[head].e-Q[head].s))>eps) tail--; 66 while(head<tail && (((Q[head]&Q[head-1])-Q[tail].s)^(Q[tail].e-Q[tail].e))>eps) head++; 67 if(tail<=head+1) return; 68 for(int i=head;i<tail; i++) res[resn++]=Q[i]&Q[i+1]; 69 if(head<tail-1) res[resn++]=Q[head]&Q[tail]; 70 } 71 double dist(point a,point b){ 72 return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); 73 } 74 void change(point p1,point p2,point &a,point &b,double p){ 75 double len=dist(p1,p2); 76 double dx=(p1.y-p2.y)*p/len,dy=(p2.x-p1.x)*p/len; 77 a.x=p1.x+dx;a.y=p1.y+dy; 78 b.x=p2.x+dx;b.y=p2.y+dy; 79 } 80 bool check(double mid){ 81 for (int i=0;i<N;i++){ 82 point a,b; 83 change(p[i],p[(i+1)%N],a,b,mid); 84 L[i]=line(a,b); 85 } 86 int resn; 87 HPI(L,N,pp,resn); //resn等于0说明移多了 88 if (resn==0) return false; else return true; 89 } 90 int main(){ 91 while (cin >> N && N){ 92 for (int i=0;i<N;i++) 93 cin >> p[i].x >> p[i].y; 94 double l=0,r=100000,mid; 95 double ans; 96 while (r-l>=eps){ 97 mid=(l+r)/2; 98 if (check(mid)){ 99 ans=mid; 100 l=mid+eps; 101 } 102 else r=mid-eps; 103 } 104 printf("%.6f ",ans); 105 } 106 return 0; 107 }
4.poj3384 Feng Shui
传送：http://poj.org/problem?id=3384
题意：给定两个同样大小的圆放置在多边形内（可以与多边形相切，两圆可以重叠），尽可能大的覆盖多边形面积，问两圆圆心。
分析：用半平面交将多边形的每条边一起向“内”推进R，得到新的多边形，然后求多边形的最远两点。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 using namespace std; 6 const double eps=1e-8; 7 const int maxn=110; 8 inline double sqr(double x){return x*x;} 9 int n; double r; 10 int sgn(double x){ 11 if (fabs(x)<eps) return 0; 12 if (x<0) return -1; 13 return 1; 14 } 15 struct point{ 16 double x,y; 17 point(){} 18 point(double _x,double _y):x(_x),y(_y){} 19 point operator -(const point &b)const{ 20 return point(x-b.x,y-b.y); 21 } 22 double operator ^(const point &b)const{ 23 return x*b.y-y*b.x; 24 } 25 }; 26 struct line{ 27 point s,e; 28 double k; //斜率 29 line(){} 30 line(point _s,point _e):s(_s),e(_e){k=atan2(e.y-s.y,e.x-s.x);} 31 point operator &(const line &b)const{ //求两直线交点 32 point res=s; 33 double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e)); 34 res.x+=(e.x-s.x)*t; res.y+=(e.y-s.y)*t; 35 return res; 36 } 37 }; 38 point p[maxn]; //记录最初给的点集 39 line L[maxn]; //由最初的点集生成直线的集合 40 point pp[maxn]; //记录半平面交的结果的点集 41 //半平面交，直线的左边代表有效区域 42 bool HPIcmp(line a,line b){ //直线排序函数 43 if(sgn(a.k-b.k)!=0) return a.k<b.k; //斜率排序 44 //斜率相同我也不知道怎么办 45 return ((a.s-b.s)^(b.e-b.s))<0; 46 } 47 void HPI(line L[],int n,point res[],int &resn){ 48 //line是半平面交的直线的集合 n是直线的条数 res是结果 49 //的点集 resn是点集里面点的个数 50 int tot=n; 51 sort(L,L+n,HPIcmp); 52 tot=1; 53 //去掉斜率重复的 54 for(int i=1;i<n;i++) if(sgn(L[i].k-L[i-1].k)!=0) L[tot++]=L[i]; 55 int head,tail; line Q[maxn]; //双端队列 56 Q[head=0]=L[0]; Q[tail=1]=L[1]; 57 resn=0; 58 for(int i=2;i<tot;i++){ 59 if(sgn((Q[tail].e-Q[tail].s)^(Q[tail-1].e-Q[tail-1].s))==0|| 60 sgn((Q[head].e-Q[head].s)^(Q[head+1].e-Q[head+1].s))==0) return; 61 while(head<tail && (((Q[tail]&Q[tail-1])-L[i].s)^(L[i].e-L[i].s))>eps) tail--; 62 while(head<tail && (((Q[head]&Q[head+1])-L[i].s)^(L[i].e-L[i].s))>eps) head++; 63 Q[++tail]=L[i]; 64 } 65 while(head<tail && (((Q[tail]&Q[tail-1])-Q[head].s)^(Q[head].e-Q[head].s))>eps) tail--; 66 while(head<tail && (((Q[head]&Q[head-1])-Q[tail].s)^(Q[tail].e-Q[tail].e))>eps) head++; 67 if(tail<=head+1) return; 68 for(int i=head;i<tail; i++) res[resn++]=Q[i]&Q[i+1]; 69 if(head<tail-1) res[resn++]=Q[head]&Q[tail]; 70 } 71 double dist(point a,point b){ 72 return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); 73 } 74 void change(point p1,point p2,point &a,point &b,double p){ 75 double len=dist(p1,p2); 76 double dx=(p1.y-p2.y)*p/len,dy=(p2.x-p1.x)*p/len; 77 a.x=p1.x+dx;a.y=p1.y+dy; 78 b.x=p2.x+dx;b.y=p2.y+dy; 79 } 80 int main(){ 81 while (cin >> n >> r){ 82 for (int i=0;i<n;i++) cin >> p[i].x >> p[i].y; 83 reverse(p,p+n); 84 for (int i=0;i<n;i++){ 85 point a,b; 86 change(p[i],p[(i+1)%n],a,b,r); 87 L[i]=line(a,b); 88 } 89 int resn; 90 HPI(L,n,pp,resn); //resn等于0说明移多了 91 int res1=0,res2=0; 92 for (int i=0;i<resn;i++) 93 for (int j=i+1;j<resn;j++){ 94 if (dist(pp[i],pp[j])>dist(pp[res1],pp[res2])) res1=i,res2=j; 95 } 96 printf("%.5f %.5f %.5f %.5f ",pp[res1].x,pp[res1].y,pp[res2].x,pp[res2].y); 97 } 98 return 0; 99 }
5.poj2540 Hotter Colder
传送：http://poj.org/problem?id=2540
题意：在10×10的房间里，有一个点放有宝藏。从（0,0）开始，每次走一个点，告诉你距离宝藏更近or更远，每次输出宝藏可能所在区域的面积。
分析：半平面交解线性规划问题。
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<string> 6 using namespace std; 7 const double eps=1e-8; 8 const int maxn=110; 9 int sgn(double x){ 10 if (fabs(x)<eps) return 0; 11 if (x<0) return -1; 12 return 1; 13 } 14 struct point{ 15 double x,y; 16 point(){} 17 point(double _x,double _y):x(_x),y(_y){} 18 point operator +(const point &b)const{ 19 return point(x+b.x,y+b.y); 20 } 21 point operator -(const point &b)const{ 22 return point(x-b.x,y-b.y); 23 } 24 double operator ^(const point &b)const{ 25 return x*b.y-y*b.x; 26 } 27 point operator *(double k)const{ 28 return point(x*k,y*k); 29 } 30 }; 31 point pp[maxn]; 32 struct line{ 33 point p,v; 34 double k; 35 line(){} 36 line(point a,point b):p(a),v(b){k=atan2(v.y,v.x);} 37 bool operator <(const line &b)const{ 38 return k<b.k; 39 } 40 }; 41 line L[maxn],q[maxn]; 42 bool left(const line &l,const point &p){ 43 return (l.v^(p-l.p))>0; //点在线的上方 44 } 45 point pos(const line &a,const line &b){ 46 point x=a.p-b.p; 47 double t=(b.v^x)/(a.v^b.v); 48 return a.p+a.v*t; 49 } 50 int HalfplaneIntersection(line L[],int n,point poly[]){ 51 sort(L,L+n); 52 int first,last; 53 point *p=new point[n]; 54 line *q=new line[n]; 55 q[first=last=0] = L[0]; 56 for(int i=1;i<n;i++){ 57 while(first < last && !left(L[i],p[last-1])) last--; 58 while(first < last && !left(L[i],p[first])) first++; 59 q[++last] = L[i]; 60 if(fabs((q[last].v^q[last-1].v))<eps) { 61 last--; 62 if(left(q[last],L[i].p)) q[last] = L[i]; 63 } 64 if(first<last) p[last-1]=pos(q[last-1],q[last]); 65 } 66 while(first<last && !left(q[first],p[last-1])) last--; 67 if(last-first <=1) return 0; 68 p[last]=pos(q[last],q[first]); 69 int m=0; 70 for(int i=first;i<=last;i++) poly[m++]=p[i]; 71 return m; 72 } 73 double dist(point a){ 74 return sqrt(a.x*a.x+a.y*a.y); 75 } 76 point normal(point b) { 77 double len=dist(b); 78 return point(-b.y/len,b.x/len); 79 } 80 double getarea(point p[],int n){ 81 double sum=0; 82 for (int i=0;i<n;i++) sum+=(p[i]^(p[(i+1)%n])); 83 return fabs(sum)/2; 84 } 85 int main(){ 86 L[0]=line(point(0,0),point(10,0)-point(0,0)); 87 L[1]=line(point(10,0),point(10,10)-point(10,0)); 88 L[2]=line(point(10,10),point(0,10)-point(10,10)); 89 L[3]=line(point(0,10),point(0,0)-point(0,10)); 90 int cnt=4; 91 double x1=0,y1=0,x2,y2; string ch; 92 int f=1; 93 while (cin >> x2 >> y2 >> ch){ 94 point a=point((x1+x2)/2,(y1+y2)/2),b; 95 if (!f){cout << "0.00 ";continue;} 96 if (ch[0]=='H') b=normal(point(x1,y1)-point(x2,y2)); 97 else if (ch[0]=='C') b=normal(point(x2,y2)-point(x1,y1)); 98 else{cout << "0.00 ";f=0;continue;} 99 L[cnt++]=line(a,b); 100 int xx=HalfplaneIntersection(L,cnt,pp); 101 if (xx==0){cout << "0.00 ";f=0;continue;} 102 else{ 103 double ans=getarea(pp,xx); 104 printf("%.2f ",ans); 105 if (sgn(ans)==0) f=0; 106 } 107 x1=x2;y1=y2; 108 } 109 return 0; 110 }
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cmath> 5 #include<string> 6 using namespace std; 7 const double eps=1e-8; 8 const int maxn=110; 9 inline double sqr(double x){return x*x;} 10 int n; double r; 11 int sgn(double x){ 12 if (fabs(x)<eps) return 0; 13 if (x<0) return -1; 14 return 1; 15 } 16 struct point{ 17 double x,y; 18 point(){} 19 point(double _x,double _y):x(_x),y(_y){} 20 point operator -(const point &b)const{ 21 return point(x-b.x,y-b.y); 22 } 23 double operator ^(const point &b)const{ 24 return x*b.y-y*b.x; 25 } 26 }; 27 struct line{ 28 point s,e; 29 double k; //斜率 30 line(){} 31 line(point _s,point _e):s(_s),e(_e){k=atan2(e.y-s.y,e.x-s.x);} 32 point operator &(const line &b)const{ //求两直线交点 33 point res=s; 34 double t=((s-b.s)^(b.s-b.e))/((s-e)^(b.s-b.e)); 35 res.x+=(e.x-s.x)*t; res.y+=(e.y-s.y)*t; 36 return res; 37 } 38 }; 39 line L[maxn]; //由最初的点集生成直线的集合 40 point pp[maxn]; //记录半平面交的结果的点集 41 //半平面交，直线的左边代表有效区域 42 bool HPIcmp(line a,line b){ //直线排序函数 43 if(sgn(a.k-b.k)!=0) return a.k<b.k; //斜率排序 44 return ((a.s-b.s)^(b.e-b.s))<0; 45 } 46 void HPI(line L[],int n,point res[],int &resn){ 47 int tot=n; 48 sort(L,L+n,HPIcmp); 49 tot=1; 50 //去掉斜率重复的 51 for(int i=1;i<n;i++) if(sgn(L[i].k-L[i-1].k)!=0) L[tot++]=L[i]; 52 int head,tail; line Q[maxn]; //双端队列 53 Q[head=0]=L[0]; Q[tail=1]=L[1]; 54 resn=0; 55 for(int i=2;i<tot;i++){ 56 if(sgn((Q[tail].e-Q[tail].s)^(Q[tail-1].e-Q[tail-1].s))==0|| 57 sgn((Q[head].e-Q[head].s)^(Q[head+1].e-Q[head+1].s))==0) return; 58 while(head<tail && (((Q[tail]&Q[tail-1])-L[i].s)^(L[i].e-L[i].s))>eps) tail--; 59 while(head<tail && (((Q[head]&Q[head+1])-L[i].s)^(L[i].e-L[i].s))>eps) head++; 60 Q[++tail]=L[i]; 61 } 62 while(head<tail && (((Q[tail]&Q[tail-1])-Q[head].s)^(Q[head].e-Q[head].s))>eps) tail--; 63 while(head<tail && (((Q[head]&Q[head-1])-Q[tail].s)^(Q[tail].e-Q[tail].e))>eps) head++; 64 if(tail<=head+1) return; 65 for(int i=head;i<tail; i++) res[resn++]=Q[i]&Q[i+1]; 66 if(head<tail-1) res[resn++]=Q[head]&Q[tail]; 67 } 68 double getarea(point p[],int n){ 69 double sum=0; 70 for (int i=0;i<n;i++) sum+=(p[i]^p[(i+1)%n]); 71 return fabs(sum)/2; 72 } 73 // 将向量 AB 逆时针旋转角度A 74 inline point Revolve(double cosA, double sinA, point A, point B){ 75 point B_; 76 B_.x = (B.x - A.x) * cosA - (B.y - A.y) * sinA + A.x; 77 B_.y = (B.x - A.x) * sinA + (B.y - A.y) * cosA + A.y; 78 return B_; 79 } 80 int main(){ 81 L[0]=line(point(0,0),point(10,0)); 82 L[1]=line(point(10,0),point(10,10)); 83 L[2]=line(point(10,10),point(0,10)); 84 L[3]=line(point(0,10),point(0,0)); 85 int cnt=4; 86 double x1=0,y1=0,x2,y2; string ch; 87 int f=1; 88 while (cin >> x2 >> y2 >> ch){ 89 point a=point((x1+x2)/2,(y1+y2)/2),b; 90 int resn; 91 if (!f){cout << "0.00 ";continue;} 92 if (ch[0]=='C'){ 93 b=Revolve(0,1,a,point(x2,y2)); 94 } 95 else if (ch[0]=='H'){ 96 b=Revolve(0,-1,a,point(x2,y2)); 97 } 98 else{cout << "0.00 ";f=0;continue;} 99 L[cnt++]=line(a,b); 100 HPI(L,cnt,pp,resn); 101 if (resn==0){cout << "0.00 ";f=0;continue;} 102 else{ 103 double area=getarea(pp,resn); 104 printf("%.2f ",area); 105 } 106 x1=x2;y1=y2; 107 } 108 return 0; 109 }