POJ 1113(Wall-Quickhull)

Language:
Wall
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 24604   Accepted: 8183

Description

King想在自己的n个城堡外建Wall,使Wall与任一城堡距离至少为L且能围住它的城堡. 


求Wall最短长度. 

Input

第一行为 N (3 <= N <= 1000) 和 L(1 <= L <= 1000).
接下来 N 行,每行为城堡坐标Xi,Yi (-10000 <= Xi, Yi <= 10000).

Output

输出一行Wall最短长度.

Sample Input

9 100
200 400
300 400
300 300
400 300
400 400
500 400
500 200
350 200
200 200

Sample Output

1628

Hint

结果四舍五入就可以了

Source

易证Wall最短长度=对城堡求凸包的周长+2πL

这里介绍一个凸包求法QuickHull

备注Quickhull-

s表示向量CACB的叉积(在上一求得,用于求距离),初始化为0

用[l,r]表示点集区间,

有2个要点

1.A,B , C的关系

(1)

(2)


2.i,j的调换

可从下图看出










#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<functional>
#include<algorithm>
#include<cctype>
using namespace std;
#define MAXN (1000+10)
#define MAXXi (10000+10)
#define eps (1e-10)
const double pi=3.1415926;
int sqr(int x) {return x*x;}
struct P
{
	int x,y;
	P(){}
	P(int _x,int _y):x(_x),y(_y){}
	friend istream& operator>>(istream &cin,P &a)
	{
		cin>>a.x>>a.y;
		return cin;
	}
	friend bool operator<(const P a,const P b){return (a.x==b.x)?a.y<b.y:a.x<b.x;}
	friend bool operator>(const P a,const P b){return (a.x==b.x)?a.y>b.y:a.x>b.x;}
}a[MAXN],st[MAXN];
double dis(P A,P B)
{
	return sqrt((double)sqr(A.x-B.x)+sqr(A.y-B.y));
}
struct V
{
	int x,y;
	V(){}
	V(int _x,int _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend int operator*(V a,V b)
	{
		return a.x*b.y-a.y*b.x;
	}
};
int n,l,size=0;
double s[MAXN]={0.0};
void hull(int l,int r,P A,P B)
{
	int p=l;
	for (int k=l;k<=r;k++)
		if (s[p]<s[k]||s[p]==s[k]&&a[p]<a[k]) p=k;
	P C=a[p];
	int i=l-1,j=r+1;
	for (int k=l;k<=r;k++)
	{
		s[++i]=V(a[k],A)*V(a[k],C);
		if (s[i]>0) /*Right*/ swap(a[i],a[k]); else i--;
	}
	for (int k=r;k>=l;k--)
	{
		s[--j]=V(a[k],C)*V(a[k],B);
		if (s[j]>0) /*Right*/ swap(a[j],a[k]); else j++;
	}
	if (l<=i) hull(l,i,A,C);
	st[++size]=C;
	if (j<=r) hull(j,r,C,B);
}
int main()
{
//	freopen("poj1113.in","r",stdin);
	cin>>n>>l;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	int pmin=1,pmax=1;
	for (int i=2;i<=n;i++)
	{
		if (a[i]<a[pmin]) pmin=i;
		if (a[i]>a[pmax]) pmax=i;
	}
	swap(a[1],a[pmin]);swap(a[n],a[pmax]);
	st[++size]=a[1];
	hull(2,n,a[1],a[1]);
//	for (int i=1;i<=size;i++) cout<<st[i].x<<' '<<st[i].y<<' '<<endl;
	double ans=0;
	for (int i=1;i<=size;i++) ans+=dis(st[i],st[i+1<=size?i+1:1]);
	cout.setf(ios::fixed);
	cout.precision(0);
	cout<<ans+2*pi*l<<endl;
	return 0;
}

POJ 1228(稳定凸包)

Language:
Grandpa's Estate
Time Limit: 1000MS   Memory Limit: 10000K
Total Submissions: 8990   Accepted: 2383

Description

Kamran the Believer继承了祖母的一个凸多边形庄园. 庄园外围用绳子和木桩围起. 但一些绳子和木桩缺失了.帮忙看一下用剩余木桩围起的庄园是否是稳定凸包(即剩下的钉子能确定一个唯一的凸包).

Input

第一行一个数据组数 t (1 <= t <= 10). 
对于每组数据,第一行为 n (1 <= n <= 1000) 表示木桩数. 接下来n行,每行为木桩坐标(x,y),保证整数.

Output

 对每组数据输出YES 或 NO ,表示其是否稳定.

Sample Input

1
6
0 0
1 2
3 4
2 0
2 4
5 0

Sample Output

NO

Source

要想让一个凸包稳定,当且仅当凸包上任意一条边有3个以上的木桩(包括端点

证明:


只要在建完凸包后,枚举,边上的第3点即可。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXT (10+10)
#define MAXN (1000+10)
//#define sqr( x ) (x*x)
int sqr(int x){return x*x;}
struct P
{
	int x,y;
	P(){}
	P(int _x,int _y):x(_x),y(_y){}
	friend istream& operator>>(istream &cin,P &a)
	{
		cin>>a.x>>a.y;return cin;
	}
	friend double dis(P a,P b)
	{
		return sqrt(double(sqr(a.x-b.x)+sqr(a.y-b.y)));
	}
}a[MAXN];
struct V
{
	int x,y;
	V(){}
	V(int _x,int _y):x(_x),y(_y){}
	V(P a,P b):x(b.x-a.x),y(b.y-a.y){}
	friend int operator*(V a,V b)
	{
		return a.x*b.y-a.y*b.x;
	}
};
int cmp(P A,P B)
{
	int temp=V(a[1],A)*V(a[1],B);
	if (temp>0) return 1;
	else if (temp==0&&dis(a[1],A)<dis(a[1],B)) return 1;
	else return 0;
}
int t,n,st[MAXN];
bool solve()
{
	int size=1;st[0]=1;
	st[1]=1;
	int j=2;
	while (j<=n)
	{
		if (size<2||V(a[st[size-1]],a[st[size]])*V(a[st[size]],a[j])>0)
		{
			st[++size]=j++;
		}
		else size--;
	}
	a[++n]=a[1];
	st[++size]=n;

	for (int i=1;i<size;i++)
	{
	/*
		int k=st[i-1]+1;
		for (;k<st[i+1];k++)
			if (k!=st[i]&&V(a[st[i]],a[st[i+1]])*V(a[st[i]],a[st[k]])==0) break;
		if (k==st[i+1]) return 0;
	*/
		int k=1;
		for (;k<n;k++)
			if (k!=st[i]&&k!=st[i+1]&&V(a[st[i]],a[st[i+1]])*V(a[st[i]],a[k])==0) break;
		if (k==n) return 0;
	}
	return size>=4;
}
int main()
{
//	freopen("poj1228.in","r",stdin);
	cin>>t;
	while (t--)
	{
		cin>>n;
		for (int i=1;i<=n;i++) cin>>a[i];
		if (n<6)
		{
			cout<<"NOn";
			continue;
		}
		int p=1;
		for (int i=2;i<=n;i++) if (a[i].x<a[p].x||(a[i].x==a[p].x)&&(a[i].y<a[p].y)) p=i;
		swap(a[1],a[p]);
		sort(a+2,a+1+n,cmp);
//		cout<<dis(P(0,0),P(1,0))<<dis(P(0,0),P(1,0));
		if (solve()) cout<<"YESn";
		else cout<<"NOn";
	}
	return 0;
}

备注:不知为何,将sqr替换成define 结果会输出"nan"……



POJ 2007(卷包裹算法(Gift Wrapping Algorithm)+ostream)

Language:
Scrambled Polygon
Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 5602   Accepted: 2664

Description

 凸包求法如图:





Input

点数不超过 50.每行输入的坐标为整数且范围在 -999..999. 数据以(0,0)开头,保证所有点必能构成凸包,除第1个点外没有点在坐标轴上或第二象限,没用三点共线.

Output

每行输出一个坐标(x,y),以(0,0)开头,逆时针输出.

Sample Input

0 0
70 -50
60 30
-30 -50
80 20
50 -60
90 -20
-30 -40
-10 -60
90 10

Sample Output

(0,0)
(-30,-40)
(-30,-50)
(-10,-60)
(50,-60)
(70,-50)
(90,-20)
(90,10)
(80,20)
(60,30)

Source


注意istream和ostream的写法

它必须是友元函数(如果是成员函数,则必须以const P为开头,这显然不行)

它返回一个指向ostream的指针,前面可以接ostream(cout<<a<<b;),还有一个元素(要输入的)   

 friend ostream& operator<<(ostream& cout,P &a)

{
cout<<"("<<a.x<<','<<a.y<<')'<<endl;
//把要输出的内容推进输出流

return cout;
}

接下来讲卷包裹算法:

我们先找到一个在凸包上的点,然后卷过去



伪代码如下:

初始化st[]=0,j=0,endpoint=P0

do

{

将endpoint加入队列st.

找到任意从P0点出发,转向最右的点P

endpoint=P

}until endpoint=P0


#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (50+10)
struct P
{
    int x,y;
    P(){}
    P(int _x,int _y):x(_x),y(_y){}
    friend ostream& operator<<(ostream& cout,P &a)
	{
		cout<<"("<<a.x<<','<<a.y<<')'<<endl;
		return cout;

	}
}a[MAXN];
struct V
{
    int x,y;
    V(){}
    V(int _x,int _y):x(_x),y(_y){}
    V(P A,P B):x(B.x-A.x),y(B.y-A.y){}
};
int operator*(V a,V b)
{
    return a.x*b.y-a.y*b.x;
}
int n,st[MAXN];
int main()
{
//	freopen("poj2007.in","r",stdin);
    int n=1;
	while (scanf("%d%d",&a[n].x,&a[n].y)!=-1) n++; //scanf读入失败返回-1
    n--;

    int endpoint=1,j=1;
	do
	{
		cout<<a[st[j++]=endpoint];
		int k=(endpoint+1)%n+1;
		for (int i=1;i<=n;i++)
			if (endpoint!=i&&V(a[endpoint],a[i])*V(a[endpoint],a[k])>0) k=i;
		endpoint=k;
	//	cout<<endpoint<<' ';
	}while (endpoint!=1);


    return 0;
}




POJ 2187(凸包GrahamScan扫描+极角排序+平面最远点对)

Language:
平面最远点对
Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 22454   Accepted: 6868

Description

求 N (2 <= N <= 50,000) 个点平面最远点对距离平方. 

Input

* 第1行:N 

接下来每行为点的坐标 x 和 y ,(x,y)(-10,000<=x,y<=10,000的整数). 

Output

输出一行,为平面最远点对距离平方. 

Sample Input

4
0 0
0 1
1 1
1 0

Sample Output

2

Hint

(0, 0) a到 (1, 1) 距离平方为 2 

Source

凸包模版题

先用GrahamScan扫描求凸包,显然最远点对在凸包上。


极角排序:

按照逆时针顺序给平面上的点集到一个点的距离排序,使得排序后所有点正好绕这个点一圈.(按距离远近从小到大排

思路:


GrahamScan扫描:







大致如此.


另补:

该题小Bug-有可能所有点在一条直线上。

这样也能求出:

Ex:

a序列(-1,0) (0,0)    (4,0)   (9,0)

则st序列重复如下操作:

(-1,1),(0,0)入队。

(4,0)入队,不左拐->(0,0)出队

队列元素<2 (4,0)入队

……


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
#define MAXN (50000+10)
double sqr(double x){return x*x;}
struct P
{
	double x,y;
	P(){}
	P(double _x,double _y):x(_x),y(_y){}
}a[MAXN],st[MAXN];
int dis2(P A,P B)
{
	return sqr(A.x-B.x)+sqr(A.y-B.y);
}
double dis(P A,P B)
{
	return sqrt(double(dis2(A,B)));
}
struct V
{
	double x,y;
	V(){}
	V(double _x,double _y):x(_x),y(_y){}
	V(P A,P B):x(B.x-A.x),y(B.y-A.y){}
};
double operator*(V a,V b)
{
	return a.x*b.y-a.y*b.x;
}
int cmp(P A,P B) //1:a>b 0:a<=b
{
	double tmp=V(a[1],A)*V(a[1],B);
	if (tmp>0) return 1;
	else if (tmp==0) return (-(dis(a[1],A)-dis(a[1],B))>0)?1:0;
	else return 0;
}
int n;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
	int p=1;
	for (int i=2;i<=n;i++) if (a[i].x<a[p].x||a[i].x==a[p].x&&a[i].y<a[p].y) p=i;
	if (p>1) swap(a[p],a[1]);
	sort(a+2,a+1+n,cmp);

	int size=1;
	st[1]=a[1];
	for (int i=2;i<=n;)
		if (size<2||V(st[size-1],st[size])*V(st[size],a[i])>0)
			st[++size]=a[i++];
		else size--;

	int ans=0;
	for (int i=1;i<size;i++)
		for (int j=i+1;j<=size;j++)
			ans=max(ans,dis2(st[i],st[j]));
	cout<<ans<<endl;


	return 0;
}