记录编号	97315	评测结果	AAAAAAAAAA
题目名称	[USACO Jan14]奶牛冰壶运动	最终得分	100
用户昵称	ys	是否通过	通过
代码语言	C++	运行时间	0.581 s
提交时间	2014-04-18 14:38:51	内存使用	3.42 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
struct node{
	long long x,y;
};
node a[50005],b[50005],s[100005];
long long ans1,ans2,top;
bool v[50005];

bool cmp(node a,node b){
	return (a.y<b.y || (a.y==b.y && a.x<b.x));
}

void init(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
		cin>>a[i].x>>a[i].y;
	for (int i=1;i<=n;i++)
		cin>>b[i].x>>b[i].y;
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp);
}

long long chaji(node z2,node z1,node z3){
	return (z2.x-z1.x)*(z3.y-z1.y)-(z3.x-z1.x)*(z2.y-z1.y);
}

void Tubao1(){
	int i,j,z1,z2,z3,temp;
	memset(s,0,sizeof(s));
	top=2;
	s[1].x=a[1].x;s[1].y=a[1].y;
	s[2].x=a[2].x;s[2].y=a[2].y;
	for (i=3;i<=n;i++){
		while (top>1 && chaji(s[top],s[top-1],a[i])<0)
			top--;
		s[++top].x=a[i].x;
		s[top].y=a[i].y;
		if (i==n) temp=top;
	}
	for (i=n-1;i>0;i--){
		while (top>1 && chaji(s[top],s[top-1],a[i])<0) top--;
		s[++top].x=a[i].x;
		s[top].y=a[i].y;
	}
	memset(v,1,sizeof(v));
	for (i=1;i<temp;i++){
		for (j=1;j<=n;j++)
		if (v[j])
			if (chaji(s[i+1],s[i],b[j])<0) 
				v[j]=false;
	}
	for (i=temp;i<top;i++){
		for (j=1;j<=n;j++)
		if (v[j])
			if (chaji(s[i+1],s[i],b[j])<0) v[j]=false;
	}
	for (i=1;i<=n;i++)
		if (v[i]) ans1++;
}
	
void Tubao2(){
	int i,j,z1,z2,z3,temp;
	memset(s,0,sizeof(s));
	top=2;
	s[1].x=b[1].x;s[1].y=b[1].y;
	s[2].x=b[2].x;s[2].y=b[2].y;
	for (i=3;i<=n;i++){
		while (top>1 && chaji(s[top],s[top-1],b[i])<0) top--;
		s[++top].x=b[i].x;
		s[top].y=b[i].y;
		if (i==n) temp=top;
	}
	for (i=n-1;i>0;i--){
		while (top>1 && chaji(s[top],s[top-1],b[i])<0) top--;
		s[++top].x=b[i].x;
		s[top].y=b[i].y;
	}
	memset(v,1,sizeof(v));
	for (i=1;i<temp;i++){
		for (j=1;j<=n;j++)
		if (v[j])
			if (chaji(s[i+1],s[i],a[j])<0) v[j]=false;
	}
	for (i=temp;i<top;i++){
		for (j=1;j<=n;j++)
		if (v[j])
			if (chaji(s[i+1],s[i],a[j])<0) v[j]=false;
	}
	for (i=1;i<=n;i++)
		if (v[i]) ans2++;
}		


void solve(){
	int i;
	long long x1,x2,y1,y2;
	bool flag;
	ans1=ans2=0;
	flag=true;
	i=1;x1=a[1].x;
	y2=y1=a[1].y;
	while (i<=n){
		if (a[i].x==x1){
			y1=min(y1,a[i].y);
			y2=max(y2,a[i].y);
			i++;
		}
		else {
			flag=false;
			break;
		}
	}
	if (flag){
		for (i=1;i<=n;i++)
			if (b[i].x==x1 && b[i].y>=y1 && b[i].y<=y2) ans1++;
	}
	else {
		flag=true;
		i=1;y1=a[1].y;
		x1=x2=a[1].x;
		while (i<=n){
			if (a[i].y==y1){
				x1=min(x1,a[i].x);
				x2=max(x2,a[i].x);
				i++;
			}
			else {
				flag=false;
				break;
			}
		}
		if (flag){
			for (i=1;i<=n;i++)
				if (b[i].y==y1 && b[i].x>=x1 && b[i].x<=x2) ans1++;
		}
		else {
			Tubao1();
		}
	}
	
	flag=true;
	i=1;x1=b[1].x;
	y2=y1=b[1].y;
	while (i<=n){
		if (b[i].x==x1){
			y1=min(y1,b[i].y);
			y2=max(y2,b[i].y);
			i++;
		}
		else {
			flag=false;
			break;
		}
	}
	if (flag){
		for (i=1;i<=n;i++)
			if (a[i].x==x1 && a[i].y>=y1 && a[i].y<=y2) ans2++;
	}
	else {
		flag=true;
		i=1;y1=b[1].y;
		x1=x2=b[1].x;
		while (i<=n){
			if (b[i].y==y1){
				x1=min(x1,b[i].x);
				x2=max(x2,b[i].x);
				i++;
			}
			else {
				flag=false;
				break;
			}
		}
		if (flag){
			for (i=1;i<=n;i++)
				if (a[i].y==y1 && a[i].x>=x1 && a[i].x<=x2) ans2++;
		}
		else {
			Tubao2();
		}
	}
	cout<<ans1<<' '<<ans2<<endl;
}

int main(){
freopen("curling.in","r",stdin);
freopen("curling.out","w",stdout);
	init();
	solve();
	
	return 0;
}