poj2540 半平面交
//poj2540//题目意思：//在一个以（0，0）和（10.0，10.0）为对角线的矩形内有 一个目标点，//一个玩家从（0，0）开始指定另一个点，另一个玩家宣布是靠近还是远去还是相同距离
//解题思路：//1.对原来的点和所指定的点所成的线段求垂直平分线，(取中点和向量旋转可获得两点)//2.根据指定的方向，再求形成的多边形（多边形的切割）：// （1）.按一定顺序用一个数组来存下所需的点，同时还要判断是否加入 多边形与直线的交点// (求交点时要注意直线是否与边重合了);// （2）.删除重复点;//3.再求形成的多边形的面积：每相邻的两个顶点和原点形成三角形来计算（叉积）。//4.保留多边形，返回步骤1。//代码如下：
#include<iostream>#include<cstdio>#include<math.h>#include<string.h>#define eps 1e-8//#define zero(x) (((x) >0 ? (x) : (-x))<eps)struct Point{double x,y;};struct tLine{Point s,e;};//两点成线double xmult(Point p1,Point p2,Point p0){return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}bool zero(double x){return (x>0.0 ? x : -x)<eps; }//求垂直平分线tLine veDiLine(Point p1,Point p2){tLine tl;tl.s.x=(p1.x+p2.x)*0.5;tl.s.y=(p1.y+p2.y)*0.5;Point p;p.x=p1.x-tl.s.x;p.y=p1.y-tl.s.y;tl.e.x=tl.s.x-p.y;tl.e.y=tl.s.y+p.x;return tl;}//判断p1,p2两点是否在l直线的同侧int same_side(Point p1,Point p2,Point l1,Point l2){return xmult(l1,p1,l2)*xmult(l1,p2,l2)>eps;}Point intersection(Point p1,Point p2,Point p3,Point p4){Point ret=p1;double t=((p1.x-p3.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p3.y))/((p1.x-p2.x)*(p3.y-p4.y)-(p3.x-p4.x)*(p1.y-p2.y));ret.x+=t*(p2.x-p1.x);ret.y+=t*(p2.y-p1.y);return ret;}//多边形切割，保证side不在线上void polygon_cut(int &n,Point *p,Point l1,Point l2,Point side){Point pp[1000];int m=0,i;for(i=0;i<n;i++){if(same_side(p[i],side,l1,l2))pp[m++]=p[i];if(!same_side(p[i],p[(i+1)%n],l1,l2)&&!(zero(xmult(p[i],l1,l2))&&zero(xmult(p[(i+1)%n],l1,l2))))pp[m++]=intersection(p[i],p[(i+1)%n],l1,l2);}n=0;for(i=0;i<m;i++)if(!i||!zero(pp[i].x-pp[i-1].x)||!zero(pp[i].y-pp[i-1].y))p[n++]=pp[i];if(zero(p[n-1].x-p[0].x)&&zero(p[n-1].y-p[0].y))n--;//这个容易忽略，切记if(n<3)n=0;}//求多边形的面积double area_of_polygon(int n,Point *p){int i;double s=0;if(n<3)return 0;for(i=0;i<n;i++)s+=p[(i+1)%n].y*(p[i].x-p[(i+2)%n].x);return fabs(s)/2.0;//若s为正值}Point pol[10000];int n;int main(){Point p,next;char str[20];double s=100.0;p.x=0.0;p.y=0.0;pol[0].x=0.0;pol[0].y=0.0;pol[1].x=10.0;pol[1].y=0.0;pol[2].x=10.0;pol[2].y=10.0;pol[3].x=0.0;pol[3].y=10.0;n=4;bool flag=true;while(~scanf("%lf %lf %s",&next.x,&next.y,str)){tLine tl;Point side;//) &&if(str[0]=='S'||!flag||(zero(p.x-next.x)&&zero(p.y-next.y))){n=0;s=0.0;printf("0.00\n");flag=false;continue;}if(str[0]=='H'){tl=veDiLine(p,next);p.x=next.x;p.y=next.y;}else if(str[0]=='C'){tl=veDiLine(p,next);}if(s>eps){polygon_cut(n,pol,tl.s,tl.e,p);s=area_of_polygon(n,pol);}printf("%.2lf\n",s);p.x=next.x;p.y=next.y;}return 0;}
