USACO JAN14 奶牛冰壶运动凸包+判定

满足条件的一定是在凸包内的，直接判断

恬不知耻的加了特判，2333

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define N 50050

using namespace std;

int n,ss[N],top,topa,topb,ans1,ans2;

bool bo=0;

struct point{

	double x,y;

}a[N],b[N],o,p[N];

double operator * (point a,point b){return a.x*b.y-b.x*a.y;}

point operator - (point a,point b){return (point){a.x-b.x,a.y-b.y};}

double dis(point a,point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

bool operator < (point a,point b){

	double s=(a-o)*(b-o);

	if(s==0) return dis(a,o)<dis(b,o);

	return s>0;

}

void graham(point *gy){

	ss[++top]=1;

	for(int i=2;i<=n;i++){

		while(top>1&&(gy[i]-gy[ss[top-1]])*(gy[ss[top]]-gy[ss[top-1]])>0) top--;

		ss[++top]=i;

	}

}

bool checka(point b){

	int l=1,r=topa,mid;

	while(l<=r){

		mid=(l+r)>>1;

		double a1=(a[ss[mid]]-a[ss[1]])*(b-a[ss[1]]);

		double a2=(a[ss[mid+1]]-a[ss[1]])*(b-a[ss[1]]);

		if(a1>=0&&a2<=0){

			if((a[ss[mid+1]]-a[ss[mid]])*(b-a[ss[mid]])>=0) return 1;

			return 0;

		}

		else{

			if(a1<0) r=mid-1;

			else l=mid+1;

		}

	}

	return 0;

}

bool checkb(point a){

	int l=topa+1,r=topb,mid;

	while(l<=r){

		mid=(l+r)>>1;

		double a1=(b[ss[mid]]-b[ss[topa+1]])*(a-b[ss[topa+1]]);

		double a2=(b[ss[mid+1]]-b[ss[topa+1]])*(a-b[ss[topa+1]]);

		if(a1>=0&&a2<=0){

			if((b[ss[mid+1]]-b[ss[mid]])*(a-b[ss[mid]])>=0) return 1;

			return 0;

		}

		else{

			if(a1<0) r=mid-1;

			else l=mid+1;

		}

	}

	return 0;

}

int main()

{

	freopen("curling.in","r",stdin);

	freopen("curling.out","w",stdout);

	scanf("%d",&n);

	int yx=1;

	for(int i=1;i<=n;i++){

		scanf("%lf%lf",&a[i].x,&a[i].y);

		if((a[i].x<a[yx].x)||(a[i].x==a[yx].x&&a[i].y<a[yx].y))yx=i;

		if(a[i].x!=0) bo=1;

	}

	o=a[yx]; swap(a[1],a[yx]);

	sort(a+2,a+n+1);

	//for(int i=1;i<=n;i++)p[i]=a[i];

	graham(a); topa=top;

	yx=1;

	for(int i=1;i<=n;i++){

		scanf("%lf%lf",&b[i].x,&b[i].y);

		if((b[i].x<b[yx].x)||(b[i].x==b[yx].x&&b[i].y<b[yx].y))yx=i;

		if(b[i].x!=0) bo=1;

	}

	if(!bo){

		printf("%d %d\n",n-1,n-1);

		return 0;

	}

	o=b[yx]; swap(b[1],b[yx]);

	sort(b+2,b+n+1);

	graham(b); topb=top;

	for(int i=1;i<=n;i++)

		if(checka(b[i]))

			ans1++;

	for(int i=1;i<=n;i++)

		if(checkb(a[i]))

			ans2++;

	printf("%d %d\n",ans1,ans2);

	return 0;

}

巴特西

USACO JAN14 奶牛冰壶运动凸包+判定

最新文章

热门文章

巴特西

USACO JAN14 奶牛冰壶运动 凸包+判定

最新文章

热门文章

USACO JAN14 奶牛冰壶运动凸包+判定