大家好，我是来填坑的~

写计算几何真是累咧，做的第一道题就让我有点不想继续做下去了（做的第一道题就卡我精度 让不让人活了！！！！）

吐槽到此为止

--------------------------我是华丽的分割线-----------------------------

好的 第一道题：poj1385（多边形求重心）

嗯 水题 求出所有三角形面积与重心 求加权和就行了

c++要记得用c++交（g++会出现坑爹问题）

code：~_~

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;

struct Point
{
	double x;
	double y;
	friend Point operator - (Point a,Point b)
	{
		Point c;
		c.x=a.x-b.x;
		c.y=a.y-b.y;
		return c;
	}
};

double det(Point a,Point b)   ///chaji
{
	return a.x*b.y-a.y*b.x;
}

int n,num_case;

int main()
{
	scanf("%d",&num_case);
	while(num_case--)
	{
		Point a,b,c;
		scanf("%d",&n);
		scanf("%lf %lf",&a.x,&a.y);
		scanf("%lf %lf",&b.x,&b.y);
		double sum=0,temp=0,x,y,x1,y1;
		x=y=0;
		for(int i=3;i<=n;i++)
		{
			scanf("%lf %lf",&c.x,&c.y);
			temp=det(b-a,c-a);
			x1=a.x+b.x+c.x;
			y1=a.y+b.y+c.y;
			x+=temp*x1;
			y+=temp*y1;
			b=c;
			sum+=temp;
		}
		x=x/(3.0*sum);
		y=y/(3.0*sum);
		printf("%.2lf %.2lf\n",x,y);
	}
	return 0;
}

--------------------------我是可爱的分割线-----------------------------

下面 第二道题：poj1584

判断一个多边形是否为凸多边形 然后看一个圆能否放在多边形内

扫描所有边 判断下一条边在哪个方向 再求出圆心到每条边的距离

code：@_@

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;

const double eps=1e-8,pi=3.141592653589;

double isqr(double a){return a*a;}
int sign(double a)
{
	if(fabs(a)<eps)return 0;
	if(a>0)return 1;
	return -1;
}

struct Point
{
	double x;
	double y;
	Point(){x=0;y=0;}
	Point(double a,double b){x=a;y=b;}
	friend Point operator +(Point a,Point b)
	{
		return Point(a.x+b.x,a.y+b.y);
	}
	friend Point operator -(Point a,Point b)
	{
		return Point(a.x-b.x,a.y-b.y);
	}
	friend bool operator ==(Point a,Point b)
	{
		if(sign(a.x-b.x)!=0)return 0;
		if(sign(a.y-b.y)!=0)return 0;
		return 1;
	}
	friend Point operator *(double a,Point b)
	{
		return Point(a*b.x,a*b.y);
	}
	friend Point operator *(Point a,double b)
	{
		return Point(a.x*b,a.y*b);
	}
	friend Point operator /(Point a,double b)
	{
		return Point(a.x/b,a.y/b);
	}
	double norm()
	{
		return sqrt(isqr(x)+isqr(y));
	}
};

double det(Point a,Point b)   ///chaji
{
	return a.x*b.y-a.y*b.x;
}

double dot(Point a,Point b)   ///dianji
{
	return a.x*b.x+a.y*b.y;
}

double dist(Point a,Point b)
{
	return (a-b).norm();
}

double dist_Point_Line(Point p,Point a,Point b)
{
	if(sign(dot(p-a,b-a))<0)return dist(p,a);
	if(sign(dot(p-b,a-b))<0)return dist(p,b);
	return fabs(det(a-p,b-p)/dist(a,b));
}

bool Point_in_Line(Point p,Point a,Point b)
{
	if((sign(det(p-a,b-a))==0)&&(sign(det(p-a,p-b))<=0))return 1;
	return 0;
}

struct Polygon
{
	int n;
	Point p[10086];
	Polygon(){}
	int Point_in_Polygon(Point q)
	{
		int num=0,s1,s2,k;
		p[0]=p[n];
		p[n+1]=p[1];
		for(int i=1;i<=n;i++)
		{
			if(Point_in_Line(q,p[i],p[i+1]))return 2;
			k=sign(det(p[i+1]-p[i],q-p[i]));
			s1=sign(p[i].y-q.y);
			s2=sign(p[i+1].y-q.y);
			if((k>0)&&(s1<=0)&&(s2>0))num++;
			if((k<0)&&(s2<=0)&&(s1>0))num++;
		}
		if(num==0)return 0;
		return 1;
	}
}P;

int n,temp,direct;
double R,X,Y,tmp;
Point p[10086];
bool flag,flag1,flag2;

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		if(n<3)break;
		scanf("%lf %lf %lf",&R,&X,&Y);
		P.n=n;
		for(int i=1;i<=n;i++)
		{
			scanf("%lf %lf",&p[i].x,&p[i].y);
			P.p[i]=p[i];
		}
		p[0]=p[n];
		p[n+1]=p[1];
		flag=flag1=flag2=1;
		direct=0;
		for(int i=1;i<=n;i++)
		{
			temp=sign(det(p[i]-p[i-1],p[i+1]-p[i]));
			if(!direct)
				direct=temp;
			if(temp*direct<0)
			{
				flag=0;
				break;
			}
		}
		if(!flag)
		{
			printf("HOLE IS ILL-FORMED\n");
			continue;
		}
		temp=P.Point_in_Polygon(Point(X,Y));
		if(temp==0)flag1=0;
		for(int i=1;i<=n;i++)
		{
			tmp=dist_Point_Line(Point(X,Y),p[i],p[i+1])-R;
			if(sign(tmp)<0)
			{
				flag2=0;
				break;
			}
		}
		if(flag1&&flag2)
			printf("PEG WILL FIT\n");
		else 
			printf("PEG WILL NOT FIT\n");
	}
	return 0;
}

--------------------------我是调皮的分割线-----------------------------

之后就是第三道题： poj2653

据说是天上掉下一大堆木棒 输出哪些木棒在最上方

考虑叉积的用法 两条线段相交满足每一条线段的两个点都在另一条线段的两边 再用并查集随便维护一下（我只是无聊而已 实际上没有必要= =）

code：·_·

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;

const double eps=1e-8;

double isqr(double a){return a*a;}
int sign(double a)
{
	if(fabs(a)<eps)return 0;
	if(a>0)return 1;
	return -1;
}

struct Point
{
	double x;
	double y;
	Point(){x=0;y=0;}
	Point(double a,double b){x=a;y=b;}
	friend Point operator +(Point a,Point b)
	{
		return Point(a.x+b.x,a.y+b.y);
	}
	friend Point operator -(Point a,Point b)
	{
		return Point(a.x-b.x,a.y-b.y);
	}
	friend bool operator ==(Point a,Point b)
	{
		if(sign(a.x-b.x)!=0)return 0;
		if(sign(a.y-b.y)!=0)return 0;
		return 1;
	}
	friend Point operator *(double a,Point b)
	{
		return Point(a*b.x,a*b.y);
	}
	friend Point operator *(Point a,double b)
	{
		return Point(a.x*b,a.y*b);
	}
	double norm()
	{
		return sqrt(isqr(x)+isqr(y));
	}
};

double det(Point a,Point b)
{
	return a.x*b.y-a.y*b.x;
}

double dot(Point a,Point b)
{
	return a.x*b.x+a.y*b.y;
}

double dist(Point a,Point b)
{
	Point c=a-b;
	return c.norm();
}

Point rotate_Point(Point a,double angle)
{
	Point c=Point(a.x*cos(angle)-a.y*sin(angle),a.x*sin(angle)+a.y*cos(angle));
	return c;
}

bool corss(Point a,Point b,Point c,Point d)
{
	return ((det(a-b,a-c)*det(a-b,a-d)<-eps)&&(det(c-d,c-a)*det(c-d,c-b)<-eps));
}

int next[100086],n;
Point p[100086][2];

int find(int p)
{
	if(next[p]==p)return p;
	next[p]=find(next[p]);
	return next[p];
}

int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)break;
		for(int i=1;i<=n+1;i++)next[i]=i;
		for(int i=1;i<=n;i++)
		{
			scanf("%lf %lf %lf %lf",&p[i][0].x,&p[i][0].y,&p[i][1].x,&p[i][1].y);
			for(int j=find(1);j<i;j=find(j+1))
			{
				if(corss(p[j][0],p[j][1],p[i][0],p[i][1]))
					next[j]=next[j+1];
			}
		}
		printf("Top sticks: %d",find(1));
		for(int i=find(find(1)+1);i<=n;i=find(i+1))
			printf(", %d",i);
		printf(".\n");
	}
	return 0;
}

--------------------------我是炫酷的分割线-----------------------------

然后是第四道题：poj1265

pick定理 一个顶点坐标均为整点的简单多边形 满足：

面积=内部顶点数+边上顶点数/2-1

没什么好说的 定理套进去就差不多了

至于这定理到底有什么用  学了再说

code：*_*

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;

const double eps=1e-8,pi=3.141592653589;

double isqr(double a){return a*a;}
int sign(double a)
{
	if(fabs(a)<eps)return 0;
	if(a>0)return 1;
	return -1;
}

struct Point
{
	double x;
	double y;
	Point(){x=0;y=0;}
	Point(double a,double b){x=a;y=b;}
	friend Point operator +(Point a,Point b)
	{
		return Point(a.x+b.x,a.y+b.y);
	}
	friend Point operator -(Point a,Point b)
	{
		return Point(a.x-b.x,a.y-b.y);
	}
	friend bool operator ==(Point a,Point b)
	{
		if(sign(a.x-b.x)!=0)return 0;
		if(sign(a.y-b.y)!=0)return 0;
		return 1;
	}
	friend Point operator *(double a,Point b)
	{
		return Point(a*b.x,a*b.y);
	}
	friend Point operator *(Point a,double b)
	{
		return Point(a.x*b,a.y*b);
	}
	friend Point operator /(Point a,double b)
	{
		return Point(a.x/b,a.y/b);
	}
	double norm()
	{
		return sqrt(isqr(x)+isqr(y));
	}
};

double det(Point a,Point b)   ///chaji
{
	return a.x*b.y-a.y*b.x;
}

double dot(Point a,Point b)   ///dianji
{
	return a.x*b.x+a.y*b.y;
}

double dist(Point a,Point b)
{
	Point c=a-b;
	return c.norm();
}

struct Polygon
{
	int n;
	Point p[10086];
	Polygon(){}
	double area()
	{
		double sum=0;
		p[0]=p[n];
		p[n+1]=p[1];
		for(int i=1;i<=n;i++)
			sum+=det(p[i+1],p[i]);
		sum/=2;
		return fabs(sum);
	}
	int iabs(double u)
	{
		if(u>=0)return int(u);
		return int(-u);
	}
	int gcd(int a,int b)
	{
		if(b==0)return a;
		return gcd(b,a%b);
	}
	int Border_Point()
	{
		int num=0;
		p[0]=p[n];
		p[n+1]=p[1];
		for(int i=1;i<=n;i++)
			num+=gcd(iabs(p[i+1].x-p[i].x),iabs(p[i+1].y-p[i].y));
		return num;
	}
	int Inside_Point()
	{
		int ans=int(area())+1-Border_Point()/2;
		return ans;
	}
}P;

int num_case,o;

int main()
{
	scanf("%d",&num_case);
	while(num_case--)
	{
		o++;
		scanf("%d",&P.n);
		for(int i=1;i<=P.n;i++)
		{
			scanf("%lf %lf",&P.p[i].x,&P.p[i].y);
			P.p[i]=P.p[i]+P.p[i-1];
		}
		printf("Scenario #%d:\n",o);
		printf("%d %d %.1lf\n\n",P.Inside_Point(),P.Border_Point(),P.area());
	}
	return 0;
}

--------------------------我是普通的分割线-----------------------------

第五道题：poj1228

就决定是你了 出来吧 凸包~

终于出现了。。。。。。

好的 看题目 一个凸包稳定要满足凸包任意一条边有3个或以上的点（很好证 自己证） 就是要注意求出的凸包只有两个点的时候要输出NO 这意味着所有点共线了

求凸包就用经典的水平序方法就行了 我写的是逆时针的 先按x轴再按y轴双关键字排序 然后扫描 如果一个点与最近加入的第二个点构成的直线的斜率小于最近加入的第一个点与最近加入的第二个点构成的直线的斜率 那么将最后加入的点弹出 直至不满足以上条件 左边扫过来 右边扫过去 凸包就求完了~ 要注意的是如果点的个数大于1 最后一个加入的点一定会是第一个点 要去掉

至于线段上有没有其他点 n^2枚举即可

code：0.0

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

const double eps=1e-8,pi=3.141592653589;

double isqr(double a){return a*a;}
int sign(double a)
{
	if(fabs(a)<eps)return 0;
	if(a>0)return 1;
	return -1;
}

struct Point
{
	double x;
	double y;
	Point(){x=0;y=0;}
	Point(double a,double b){x=a;y=b;}
	friend Point operator +(Point a,Point b)
	{
		return Point(a.x+b.x,a.y+b.y);
	}
	friend Point operator -(Point a,Point b)
	{
		return Point(a.x-b.x,a.y-b.y);
	}
	friend bool operator ==(Point a,Point b)
	{
		if(sign(a.x-b.x)!=0)return 0;
		if(sign(a.y-b.y)!=0)return 0;
		return 1;
	}
	friend Point operator *(double a,Point b)
	{
		return Point(a*b.x,a*b.y);
	}
	friend Point operator *(Point a,double b)
	{
		return Point(a.x*b,a.y*b);
	}
	friend Point operator /(Point a,double b)
	{
		return Point(a.x/b,a.y/b);
	}
	double norm()
	{
		return sqrt(isqr(x)+isqr(y));
	}
};

double det(Point a,Point b)   ///chaji
{
	return a.x*b.y-a.y*b.x;
}

double dot(Point a,Point b)   ///dianji
{
	return a.x*b.x+a.y*b.y;
}

double dist(Point a,Point b)
{
	Point c=a-b;
	return c.norm();
}

Point rotate_Point(Point a,double angle)
{
	Point c=Point(a.x*cos(angle)-a.y*sin(angle),a.x*sin(angle)+a.y*cos(angle));
	return c;
}

struct Line
{
	Point a;
	Point b;
	Line(){}
	Line(Point a1,Point b1){a=a1;b=b1;}
};

double dist_Point_Line(Point p,Point a,Point b)
{
	if(sign(dot(p-a,b-a))<0)return dist(p,a);
	if(sign(dot(p-b,a-b))<0)return dist(p,b);
	return fabs(det(a-p,b-p)/dist(a,b));
}

Point pedal(Point p,Point a,Point b)
{
	Point P;
	double tmp=dot(b-a,p-a)/dot(b-a,b-a);
	P=a+tmp*(b-a);
	return P;
}

bool Point_in_Line(Point p,Point a,Point b)
{
	if((sign(det(p-a,b-a))==0)&&(sign(det(p-a,p-b))<=0))return 1;
	return 0;
}

bool parallel(Line p,Line q)
{
	if(sign(det(p.a-p.b,q.a-q.b)))return 1;
	return 0;
}

bool make_Point(Line p,Line q,Point &key)
{
	if(parallel(p,q))return 0;
	double s1=det(p.a-q.a,p.b-q.b),s2=det(p.b-q.a,p.b-q.b);
	key=(s1*p.b-s2*p.a)/(s1-s2);
	return 1;
}

Line move_Line(Line l,Line direct,double dis)
{
	Point p=direct.b-direct.a;
	p=p/p.norm();
	return Line(l.a+p*dis,l.b+p*dis);
}

struct Convex_Polygon
{
	vector<Point>p;
	Convex_Polygon(int u=0){p.resize(u);}
}p;

bool cmp_Convex_Polygon(Point a,Point b)
{
	if(sign(a.x-b.x)==0)return (sign(a.y-b.y)<0);
	return (sign(a.x-b.x)<0);
}

Convex_Polygon get_Convex_Polygon(vector<Point>&a)
{
	Convex_Polygon ans(a.size()*2+3);
	sort(a.begin(),a.end(),cmp_Convex_Polygon);
	a.erase(unique(a.begin(),a.end()),a.end());
	int n=0,tmp;
	for(int i=0;i<int(a.size());i++)
	{
		while((n>1)&&(sign(det(ans.p[n-1]-ans.p[n-2],a[i]-ans.p[n-2]))<=0))n--;
		ans.p[n++]=a[i];
	}
	tmp=n;
	for(int i=int(a.size())-2;i>=0;i--)
	{
		while((n>tmp)&&(sign(det(ans.p[n-1]-ans.p[n-2],a[i]-ans.p[n-2]))<=0))n--;
		ans.p[n++]=a[i];
	}
	if(a.size()>1)ans.p.resize(n-1);
	else ans.p.resize(n);
	return ans;
}

int main()
{
	int num_case,n;
	bool flag=0;
	vector<Point>a;
	Point P;
	scanf("%d",&num_case);
	while(num_case--)
	{
		a.resize(0);
		flag=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%lf %lf",&P.x,&P.y);
			a.push_back(P);
		}
		p=get_Convex_Polygon(a);
		n=p.p.size();
		for(int i=0;i<n;i++)
		{
			flag=0;
			for(int j=0;j<int(a.size());j++)
			{
				if(a[j]==p.p[i])continue;
				if(a[j]==p.p[(i+1)%n])continue;
				if(Point_in_Line(a[j],p.p[i],p.p[(i+1)%n]))flag=1;
			}
			if(flag==0)break;
		}
		if(p.p.size()<=2)printf("NO\n");
		else if(flag==0)printf("NO\n");
		else printf("YES\n");
	}
	return 0;
}

--------------------------我是二逼的分割线-----------------------------

第六道题：poj1264

嘛 还是凸包

这次就是要求n个凸包 求出每个凸包的面积（这个不用我讲了吧） 然后判断一个点是否位于凸包内 如果是ans加上所在凸包面积 一个凸包只算一次 不要加多了

判点是否在凸包内我写了两个 一个是O(n)的判断点在一条边的哪个方向 一个是O(logn)的二分判断 这种我不是特别懂 先放着慢慢理解吧~（没办法 蒟蒻就是蒟蒻）

code：^_^

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

const double eps=1e-8,pi=3.141592653589;

double isqr(double a){return a*a;}
int sign(double a)
{
	if(fabs(a)<eps)return 0;
	if(a>0)return 1;
	return -1;
}

struct Point
{
	double x;
	double y;
	Point(){x=0;y=0;}
	Point(double a,double b){x=a;y=b;}
	friend Point operator +(Point a,Point b)
	{
		return Point(a.x+b.x,a.y+b.y);
	}
	friend Point operator -(Point a,Point b)
	{
		return Point(a.x-b.x,a.y-b.y);
	}
	friend bool operator ==(Point a,Point b)
	{
		if(sign(a.x-b.x)!=0)return 0;
		if(sign(a.y-b.y)!=0)return 0;
		return 1;
	}
	friend Point operator *(double a,Point b)
	{
		return Point(a*b.x,a*b.y);
	}
	friend Point operator *(Point a,double b)
	{
		return Point(a.x*b,a.y*b);
	}
	friend Point operator /(Point a,double b)
	{
		return Point(a.x/b,a.y/b);
	}
	double norm()
	{
		return sqrt(isqr(x)+isqr(y));
	}
};

double det(Point a,Point b)   ///chaji
{
	return a.x*b.y-a.y*b.x;
}

double dot(Point a,Point b)   ///dianji
{
	return a.x*b.x+a.y*b.y;
}

double dist(Point a,Point b)
{
	Point c=a-b;
	return c.norm();
}

Point rotate_Point(Point a,double angle)
{
	Point c=Point(a.x*cos(angle)-a.y*sin(angle),a.x*sin(angle)+a.y*cos(angle));
	return c;
}

struct Line
{
	Point a;
	Point b;
	Line(){}
	Line(Point a1,Point b1){a=a1;b=b1;}
};

double dist_Point_Line(Point p,Point a,Point b)
{
	if(sign(dot(p-a,b-a))<0)return dist(p,a);
	if(sign(dot(p-b,a-b))<0)return dist(p,b);
	return fabs(det(a-p,b-p)/dist(a,b));
}

Point pedal(Point p,Point a,Point b)
{
	Point P;
	double tmp=dot(b-a,p-a)/dot(b-a,b-a);
	P=a+tmp*(b-a);
	return P;
}

bool Point_in_Line(Point p,Point a,Point b)
{
	if((sign(det(p-a,b-a))==0)&&(sign(det(p-a,p-b))<=0))return 1;
	return 0;
}

bool parallel(Line p,Line q)
{
	if(sign(det(p.a-p.b,q.a-q.b)))return 1;
	return 0;
}

bool make_Point(Line p,Line q,Point &key)
{
	if(parallel(p,q))return 0;
	double s1=det(p.a-q.a,p.b-q.b),s2=det(p.b-q.a,p.b-q.b);
	key=(s1*p.b-s2*p.a)/(s1-s2);
	return 1;
}

Line move_Line(Line l,Line direct,double dis)
{
	Point p=direct.b-direct.a;
	p=p/p.norm();
	return Line(l.a+p*dis,l.b+p*dis);
}

struct Convex_Polygon
{
	vector<Point>p;
	Convex_Polygon(int u=0){p.resize(u);}
	double area()
	{
		int n=p.size();
		double sum=0.0;
		for(int i=0;i<n;i++)
			sum+=det(p[(i+1)%n],p[i]);
		sum/=2;
		return fabs(sum);
	}
}p[100];

bool cmp_Convex_Polygon(Point a,Point b)
{
	if(sign(a.x-b.x)==0)return (sign(a.y-b.y)<0);
	return (sign(a.x-b.x)<0);
}

Convex_Polygon get_Convex_Polygon(vector<Point>a)
{
	Convex_Polygon ans(a.size()*2+3);
	sort(a.begin(),a.end(),cmp_Convex_Polygon);
	a.erase(unique(a.begin(),a.end()),a.end());
	int n=0,tmp;
	for(int i=0;i<int(a.size());i++)
	{
		while((n>1)&&(sign(det(ans.p[n-1]-ans.p[n-2],a[i]-ans.p[n-2]))<=0))n--;
		ans.p[n++]=a[i];
	}
	tmp=n;
	for(int i=int(a.size())-2;i>=0;i--)
	{
		while((n>tmp)&&(sign(det(ans.p[n-1]-ans.p[n-2],a[i]-ans.p[n-2]))<=0))n--;
		ans.p[n++]=a[i];
	}
	if(a.size()>1)ans.p.resize(n-1);
	else ans.p.resize(n);
	return ans;
}

bool containOn(Convex_Polygon a,Point p)
{
	int n=a.p.size(),direction=0,tmp;
	for(int i=0;i<n;i++)
	{
		tmp=sign(det(a.p[i]-p,a.p[(i+1)%n]-p));
		if(tmp)
		{
			if(direction!=0)
			{
				if(tmp!=direction)
					return 0;
			}
			else 
				direction=tmp;
		}
	}
	return 1;
}

int containOlogn(Convex_Polygon a,Point p)
{
	int n=a.p.size(),l=0,r=a.p.size(),tmp,mid;
	Point q=(a.p[0]+a.p[n/3]+a.p[(2*n)/3])/3.0;
	while(l+1<r)
	{
		mid=(l+r)>>1;
		if(sign(det(a.p[l]-q,a.p[mid]-q))>0)
		{
			if((sign(det(a.p[l]-q,p-q))>=0)&&(sign(det(a.p[mid]-q,p-q))<0))r=mid;
			else l=mid;
		}
		else 
		{
			if((sign(det(a.p[l]-q,p-q))<0)&&(sign(det(a.p[mid]-q,p-q))>=0))l=mid;
			else r=mid;
		}
	}
	r%=n;
	tmp=sign(det(a.p[r]-p,a.p[l]-p));
	if(tmp==-1)return 1;
	if(tmp==0)return 2;
	return 0;
}

int main()
{
	int n,num_p=0;
	bool visit[100]={0};
	double ans=0.0,area[100]={0};
	vector<Point>a;
	Point P;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==-1)break;
		a.resize(0);
		for(int i=1;i<=n;i++)
		{
			scanf("%lf %lf",&P.x,&P.y);
			a.push_back(P);
		}
		p[++num_p]=get_Convex_Polygon(a);
		area[num_p]=p[num_p].area();
	}
	while(scanf("%lf %lf",&P.x,&P.y)!=EOF)
	{
		for(int i=1;i<=num_p;i++)
			if(containOlogn(p[i],P))
				if(!visit[i])
				{
					ans+=area[i];
					visit[i]=1;
				}
	}
	printf("%.2lf\n",ans);
	system("pause");
	return 0;
}

--------------------------我是文艺的分割线-----------------------------

第七道题：poj2187

这算是经典题目了 平面内最远点对

不用我说最远点对一定位于点集的凸包上了吧 然后上旋转卡壳（据说四个多音字可以有2^4种读法 请自行找一个最顺口的） 这东西我也说不清楚 就是证明一个单调性 然后吧啦吧啦跳点 然后就取最大值就行了（原谅我这么不负责任吧） 想具体了解找别的博客吧（说不准某天我也心血来潮写了写什么的）反正我就这么写了

code：#。#

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <cmath>
using namespace std;

const double eps=1e-8,pi=3.141592653589;

double isqr(double a){return a*a;}
int sign(double a)
{
	if(fabs(a)<eps)return 0;
	if(a>0)return 1;
	return -1;
}

struct Point
{
	double x;
	double y;
	Point(){x=0;y=0;}
	Point(double a,double b){x=a;y=b;}
	friend Point operator +(Point a,Point b)
	{
		return Point(a.x+b.x,a.y+b.y);
	}
	friend Point operator -(Point a,Point b)
	{
		return Point(a.x-b.x,a.y-b.y);
	}
	friend bool operator ==(Point a,Point b)
	{
		if(sign(a.x-b.x)!=0)return 0;
		if(sign(a.y-b.y)!=0)return 0;
		return 1;
	}
	friend Point operator *(double a,Point b)
	{
		return Point(a*b.x,a*b.y);
	}
	friend Point operator *(Point a,double b)
	{
		return Point(a.x*b,a.y*b);
	}
	friend Point operator /(Point a,double b)
	{
		return Point(a.x/b,a.y/b);
	}
	double norm()
	{
		return sqrt(isqr(x)+isqr(y));
	}
};

double det(Point a,Point b)   ///chaji
{
	return a.x*b.y-a.y*b.x;
}

double dot(Point a,Point b)   ///dianji
{
	return a.x*b.x+a.y*b.y;
}

double dist(Point a,Point b)
{
	Point c=a-b;
	return c.norm();
}

struct Convex_Polygon
{
	vector<Point>p;
	Convex_Polygon(int u=0){p.resize(u);}
	double area()
	{
		int n=p.size();
		double sum=0;
		for(int i=0;i<n;i++)
			sum+=det(p[(i+1)%n],p[i]);
		sum/=2;
		return fabs(sum);
	}
}p;

bool cmp_Convex_Polygon(Point a,Point b)
{
	if(sign(a.x-b.x)==0)return (sign(a.y-b.y)<0);
	return (sign(a.x-b.x)<0);
}

Convex_Polygon get_Convex_Polygon(vector<Point>a)
{
	Convex_Polygon ans(a.size()*2+3);
	sort(a.begin(),a.end(),cmp_Convex_Polygon);
	a.erase(unique(a.begin(),a.end()),a.end());
	int n=0,tmp;
	for(int i=0;i<int(a.size());i++)
	{
		while((n>1)&&(sign(det(ans.p[n-1]-ans.p[n-2],a[i]-ans.p[n-2]))<=0))n--;
		ans.p[n++]=a[i];
	}
	tmp=n;
	for(int i=int(a.size())-2;i>=0;i--)
	{
		while((n>tmp)&&(sign(det(ans.p[n-1]-ans.p[n-2],a[i]-ans.p[n-2]))<=0))n--;
		ans.p[n++]=a[i];
	}
	if(a.size()>1)ans.p.resize(n-1);
	else ans.p.resize(n);
	return ans;
}

double Convex_Polygon_Diameter(Convex_Polygon a,int &p,int &q)
{
	int n=a.p.size();
	double max_dis=0.0,dis=0.0;
	if(n==1)
	{
		p=q=0;
		return max_dis;
	}
	for(int i=0,j=1;i<n;i++)
	{
		while(sign(det(a.p[(i+1)%n]-a.p[i],a.p[j]-a.p[i])-det(a.p[(i+1)%n]-a.p[i],a.p[(j+1)%n]-a.p[i]))<0)j=(j+1)%n;
		dis=dist(a.p[i],a.p[j]);
		if(max_dis<dis)
		{
			max_dis=dis;
			p=i;
			q=j;
		}
		dis=dist(a.p[(i+1)%n],a.p[(j+1)%n]);
		if(max_dis<dis)
		{
			max_dis=dis;
			p=(i+1)%n;
			q=(j+1)%n;
		}
	}
	return max_dis*max_dis;
}

int main()
{
	int n,l,r,ans;
	Point P;
	vector<Point>a;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf %lf",&P.x,&P.y);
		a.push_back(P);
	}
	p=get_Convex_Polygon(a);
	ans=int(Convex_Polygon_Diameter(p,l,r));
	printf("%d\n",ans);
	return 0;
}

--------------------------我是%&#~￥#的分割线-----------------------------

    这两个周六刷题的成果就这么多了 代码其实是因为找不到好用的插件才没贴 原谅我吧 过些天一定把代码补上

以下是看完此文的一些问题与回答：

Q:为什么没有半平面交? A:对不起 我还没学会 = =

Q:圆并圆交在哪里? A:那是什么可以吃吗？

Q:三维的计算几何呢? A:不好意思 我更愿意留在二维世界

。。。。。。

To Be Continued