TIOJ 1580 火星圍棋（go） ( 97北市賽 prob 5 )

poao899    44K    123MS    G++     2.31K     2009-11-17 10:51:02                                  .

當年噁爆的防破台題|||


凸包+Graph= =

被捏很大才寫得出來囧

//***************************

//go ( prob 5 ) Convex Hull + Floyd Warshall

#include<stdio.h>
#include<algorithm>
struct node{
	int x,y;
	bool outPoly;
	bool operator<(const node &b)const{
		return x==b.x?y<b.y:x<b.x;
	}
}R[101],B[101];
int r,b;
struct edge{
	int i,j;
	edge *next;
}E[20000],*V[101];
int dis[101][101];
int edgeCnt;
int cross(node p,node a,node b){
	a.x-=p.x;
	a.y-=p.y;
	b.x-=p.x;
	b.y-=p.y;
	//printf("cross %d\n",a.x*b.y - a.y*b.x);
	return a.x*b.y - a.y*b.x;
}
void test(int a,int b){
	//printf("%d %d\n",a,b);
	for(int i=0;i<r;i++)
		if(!R[i].outPoly)
			if(cross(B[a],B[b],R[i])>0)
				return;
	edge *p=&E[edgeCnt++];
	p->i=a;
	p->j=b;
	edge *q=V[a];
	V[a]=p;
	p->next=q;
	dis[a][b]=1;
	//printf("construct!!\n");
}
int stack[2000],top;
main(){
	//Initialize
	edgeCnt=0;
	top=0;
	for(int i=0;i<101;i++)
		for(int j=0;j<101;j++)
			dis[i][j]=100000;
	//Input
	scanf("%d%d",&b,&r);
	for(int i=0;i<b;i++)
		scanf("%d%d",&B[i].x,&B[i].y);
	for(int i=0;i<r;i++){
		scanf("%d%d",&R[i].x,&R[i].y);
		R[i].outPoly=0;
	}
	//Convex Hull
	std::sort(B,B+b);
	stack[top++]=0;
	stack[top]=1;
	for(int i=2;i<b;i++){
		while(top>0&&cross(B[stack[top-1]] , B[stack[top]] , B[i])>=0)
			top--;
		top++;
		stack[top]=i;
	}
	int nTop=top;
	for(int i=b-2;i>=0;i--){
		while(top>nTop&&cross(B[stack[top-1]] , B[stack[top]] , B[i])>=0)
			top--;
		top++;
		stack[top]=i;
	}
	//printf("nTop %d %d\n",nTop,top);
	//for(int i=0;i<=top;i++)
		//printf("%d %d\n",B[stack[i]].x,B[stack[i]].y);
	//InPoly
	int c=0;
	for(int i=0;i<r;i++){
		int dir=cross(B[stack[0]],B[stack[1]],R[i])>0?1:-1;
		for(int j=2;j<=top;j++)
			if(dir*(cross(B[stack[j-1]],B[stack[j]],R[i]))<0){
				R[i].outPoly=1;
				c++;
				break;
		}
		//printf("%d %d Outpoly?%d\n",R[i].x,R[i].y,R[i].outPoly);
	}
	if(c==r){printf("%d\n",r*111);return 0;}
	//Construct
	for(int i=0;i<b;i++){
		//printf("%d %d\n",B[i].x,B[i].y);
		for(int j=0;j<b;j++)
			if(i!=j)
				test(i,j);
	}
	//Floyd Warshall
	for(int k=0;k<b;k++)
		for(int i=0;i<b;i++)
			for(int j=0;j<b;j++)
				if(dis[i][k]+dis[k][j]<dis[i][j])
					dis[i][j]=dis[i][k]+dis[k][j];
	//Output
	int cnt=0,minCycle=100000;
	for(int i=0;i<r;i++)
		if(R[i].outPoly)
			cnt++;
	for(int i=0;i<b;i++)
		minCycle<?=dis[i][i];
	printf("%d\n",cnt*111+minCycle*20);

}