using namespace __W_L_J__;

北京培训 DAY1

早上考试下午讲课感觉挺累的

考试：

第一题

给定一系列对于点的操作包括旋转与平移询问一个点（0，0）在应用Q_l到Q_r这些变换后得到的点

矩阵+线段树或者矩阵+逆矩阵再或者分块+矩阵

平移矩阵为3*3的旋转矩阵为2*2的于是对平移建立矩阵

1	0	0
0	1	0
Δx	Δy	1

对于旋转建立矩阵

cosα	sinα	0
-sinα	cosα	0
0	0	1

然后我们再以[x,y,1]去乘他们最后得到的[x＇,y＇,1]中的x＇，y＇就是答案。

第二题在一堆平面点中求一个包含k个点（其中必须包括x坐标y坐标字典序最小的点）的周长最大的凸包

n，k小于100的时候我们可以先求出凸包然后用DP求解 f[i][j]表示到达i这个点经过j个点的最长距离

f[i][j]=max(f[k][j-1]+dist(k,i))(k=1...i)

可惜数据范围是n,k<=1000 就需要有DP优化然后出题人很高兴的告诉我们要用一个%^$%^#@%&$&办法去优化（反正我没听懂）然后告诉了我们出自一篇名为Finding extremal polygons论文（下过来后发现这英文论文全看不懂）然后...再见

第三题有生之年第一道提交答案题

给一张01图让找出其中最大的圆的坐标以及半径

我写了一个半小时的各种程序乱搞才弄出两个点后来发现zhuohan1234在用肉眼对着数据乱搞还弄出了8个点（Orz zhuohan1234）人都气傻了= = 最后出题人告诉我们正解就是乱搞先用程序给原数据降噪再用bmp 用gdi 用ps什么的开始肉眼乱搞 = =

。。。。。。

于是提交答案题给我留下了不可磨灭的不良印象

下午的讲课（据说是随机化）怎么都听不懂啊

一开始就先讲了bitcoin的工作原理之后就开始讲丧心病狂卡hash 随机化 hash 最小圆覆盖随机增量法最近点对凸包（2D+3D） voronoi图 Delaunay三角剖分所有圆是否有交点（随机增量扫描线二分）查询点所属区间扫描线+平衡树（在线主席平衡树） &%￥%/&￥#*@@*&+%*......

人类们为何创造出了这么多奇奇怪怪丧心病狂的东西啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！！！！！

就这样吧

计算几何 PART 1

大家好，我是来填坑的~

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

吐槽到此为止

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

好的第一道题：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

« 上一页 1 2 3 4 5 6 7 8 9 10 11 下一页 »

using namespace __W_L_J__;

北京培训 DAY1

计算几何 PART 1

__W_L_J__

链接

分类

日历

二月
日	一	二	三	四	五	六
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29