记录编号	213981	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]奶牛冰壶运动	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	0.188 s
提交时间	2015-12-13 20:15:44	内存使用	2.07 MiB

//Graham
#define MAXN 50010UL

#define ll long long

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

struct Point{
	ll x,y;
	inline friend bool operator < (Point a,Point b){
		return (a.x==b.x)?(a.y<b.y):(a.x<b.x);
	}
	inline friend Point operator - (Point a,Point b){
		return (Point){a.x-b.x,a.y-b.y};//exactly vector
	}
	inline friend bool operator != (Point a,Point b){
		return a.x!=b.x||a.x!=b.y;
	}
	inline void in(){
		scanf("%lld%lld",&x,&y);
		return;
	}
};

int n,Ans1,Ans2,sta[MAXN];
Point TeamA[MAXN],TeamB[MAXN];
std::vector<Point> Convex;
bool vist[MAXN];

inline ll Cross(Point a,Point b){
	return a.x*b.y-b.x*a.y;
}

inline bool Across(Point a,Point b,Point c){
	return Cross(b-a,c-a)>0LL;//Anti_Clock
}

inline void Graham(Point p[]){
	Convex.clear();
	sta[0]=0;
	memset(vist,false,sizeof(vist));
	std::sort(p+1,p+n+1);
	sta[++sta[0]]=1;
	sta[++sta[0]]=2;
	for(int i=3;i<=n;i++){
		while(sta[0]>1&&(!Across(p[sta[sta[0]]],p[i],p[sta[sta[0]-1]])||!Cross(p[i]-p[sta[sta[0]]],p[i]-p[sta[sta[0]-1]]))) sta[0]--;
		sta[++sta[0]]=i;
	}
	for(int i=1;i<=sta[0];i++) vist[sta[i]]=true,Convex.push_back(p[sta[i]]);
	sta[0]=0;
	sta[++sta[0]]=n;
	sta[++sta[0]]=n-1;
	for(int i=n-2;i>0;i--){
		while(sta[0]>1&&(Across(p[sta[sta[0]]],p[sta[sta[0]-1]],p[i])||!Cross(p[i]-p[sta[sta[0]]],p[i]-p[sta[sta[0]-1]]))) sta[0]--;
		sta[++sta[0]]=i;
	}
	for(int i=1;i<=sta[0];i++)
		if(!vist[sta[i]]) Convex.push_back(p[sta[i]]);
	return;
}

//find first one ax->rf is AntiClock

inline int sign(int p){
	if(p<0) return -1;
	if(!p) return 0;
	return 1;
}

inline bool Covered(Point p){
	if(Convex.size()==2){
		return sign(p.x-Convex[0].x)*sign(p.x-Convex[1].x)!=1&&sign(p.y-Convex[0].y)*sign(p.y-Convex[1].y)!=1; 
	}
	int l=1,r=Convex.size()-1,mid,Ans=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(Across(Convex[0],p,Convex[mid])) Ans=mid,r=mid-1;
		else l=mid+1;
	}
	if(Ans==-1||Ans==1) return false;
	return Across(p,Convex[Ans-1],Convex[Ans]);
}

inline int Cal(Point Cov[],Point Sur[]){
	int Ans=0;
	Graham(Cov);
	for(int i=1;i<=n;i++)
		if(Covered(Sur[i])) Ans++;
	return Ans;
}

int main(){
	freopen("curling.in","r",stdin);
	freopen("curling.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) TeamA[i].in();
	for(int i=1;i<=n;i++) TeamB[i].in();
	Ans1=Cal(TeamA,TeamB);
	Ans2=Cal(TeamB,TeamA);
	printf("%d %d\n",Ans1,Ans2);
	return 0;
}