比赛 20140418 评测结果 AAAAAAAAAW
题目名称 奶牛冰壶运动 最终得分 90
用户昵称 LuciFer_T-J 运行时间 0.258 s
代码语言 C++ 内存使用 11.76 MiB
提交时间 2014-04-18 10:26:48
显示代码纯文本
#include<cstring>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;
#define MAXN 500005
struct node{
	int x,y;
}a[MAXN],b[MAXN],q[MAXN];
int n,l,r,ans;
long long S,S2;

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

long long  CJ(node a,node b,node c){
	long long  x1=b.x-a.x,y1=b.y-a.y,x2=c.x-a.x,y2=c.y-a.y;
	return x1*y2-x2*y1;
}

long long abc(long long a){
	return a<0?-a:a;
}
int main(){
	freopen("curling.in","r",stdin);
	freopen("curling.out","w",stdout);
	int i,j;
	scanf("%d",&n);
	for (i=1;i<=n;i++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	for (i=1;i<=n;i++){
		scanf("%d%d",&b[i].x,&b[i].y);
	}
	sort(a+1,a+n+1,comp);
	sort(b+1,b+n+1,comp);
	// work(A)
	l=r=1;
	q[1]=a[1];
	for (i=2;i<=n;i++){
		while (r-l>0 && CJ(q[r-1],q[r],a[i])<=0) r--;
		q[++r]=a[i];
	}
	l=r;
	for (i=n-1;i;i--){
		while (r-l>0 && CJ(q[r-1],q[r],a[i])<=0) r--;
		q[++r]=a[i];
	}
	r--;
	S=0;
	for (i=2;i<r;i++){
		S+=CJ(q[1],q[i],q[i+1]);
	}
	ans=0;
	for (i=1;i<=n;i++){
		S2=0;
		for (j=1;j<r;j++){
			S2+=fabs(CJ(b[i],q[j],q[j+1]));
		}
		S2+=abc(CJ(b[i],q[r],q[1]));
		if (S2==S) ans++;
	}
	cout<<ans<<" ";
	//work(B)
	l=r=1;
	q[1]=b[1];
	for (i=2;i<=n;i++){
		while (r-l>0 && CJ(q[r-1],q[r],b[i])<=0) r--;
		q[++r]=b[i];
	}
	l=r;
	for (i=n-1;i;i--){
		while (r-l>0 && CJ(q[r-1],q[r],b[i])<=0) r--;
		q[++r]=b[i];
	}
	S=0;
	r--;
	for (i=2;i<r;i++){
		S+=CJ(q[1],q[i],q[i+1]);
	}
	ans=0;
	for (i=1;i<=n;i++){
		S2=0;
		for (j=1;j<r;j++){
			S2+=abc(CJ(a[i],q[j],q[j+1]));
		}
		S2+=fabs(CJ(a[i],q[r],q[1]));
		if (S2==S) ans++;
	}
	cout<<ans<<endl;
}