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;
}