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-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
",ans1,ans2);
	return 0;
}