比赛 20140418 评测结果 AWWWWWWWWW
题目名称 奶牛冰壶运动 最终得分 10
用户昵称 OI永别 运行时间 0.180 s
代码语言 C++ 内存使用 4.13 MiB
提交时间 2014-04-18 10:29:06
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 100001
struct arr{
	int x,y;
}s1[N],s2[N],a[N],b[N],ss[N];
int top1,top2;
int n;
int are1,are2;
inline int sqr(int x){
	return x * x;
}

bool comp(const arr &a,const arr & b){
	if (a.y < b.y) return 1;
	if (a.y > b.y) return 0;
	return a.x < b.x;
}

inline int angle(const arr &a,const arr & b,const arr & c){// ab ×ac 逆时针>0  
	int p1 = b.x - a.x,q1 = b.y - a.y;
	int p2 = c.x - a.x,q2 = c.y - a.y;
	return p1 * q2 - p2 * q1;
}

void work1(){
	sort(a + 1,a + 1 + n,comp);
	s1[++top1] = a[1];
	s1[++top1] = a[2];
	for (int i = 3;i <= n; i++){
		while (top1 > 1 && angle(s1[top1 - 1],s1[top1],a[i]) < 0) top1 --;
		s1[++top1] = a[i];
	}
	for (int i = n; i >= 1; i--){
		while (top1 > 1 && angle(s1[top1 - 1],s1[top1],a[i]) < 0) top1 --;
		s1[++top1] = a[i];
	}
	return;
}


void work2(){
	sort(b + 1,b + 1 + n,comp);
	s2[++top2] = b[1];
	s2[++top2] = b[2];
	for (int i = 3;i <= n; i++){
		while (top2 > 1 && angle(s2[top2 - 1],s2[top2],b[i]) < 0) top2 --;
		s2[++top2] = b[i];
	}
	for (int i = n; i >= 1; i--){
		while (top2 > 1 && angle(s2[top2 - 1],s2[top2],b[i]) < 0) top2 --;
		s2[++top2] = b[i];
	}
	return;
}

inline double dis(arr a,arr b){
	return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}

bool check(arr a,arr b,arr c){
	if (dis(a,c) < dis(a,b) + dis(b,c)) return 0;
	else return 1;
}

void gets1(){
	arr node;
	node.x = node.y = 0;
	are1 = 0;
	for (int i = 1; i< top1; i++){
		are1 += angle(node,s1[i],s1[i + 1]);
	}
	are1 = abs(are1);
}

void gets2(){
	arr node;node.x = node.y = 0;
	are2 = 0;
	for (int i = 1; i< top2; i++){
		are2 += angle(node,s2[i],s2[i + 1]);
	}
	are2 = abs(are2);
}

int main(){
	freopen("curling.in","r",stdin);
	freopen("curling.out","w",stdout);
	scanf("%d",&n);	
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	memset(s1,0,sizeof(s1));
	memset(s2,0,sizeof(s2));
	for (int i = 1; i <= n; i ++){
		scanf("%d%d",&a[i].x,&a[i].y);
	}
	for (int j = 1; j <= n; j++){
		scanf("%d%d",&b[j].x,&b[j].y);
	}
	work1();
	work2();
	gets1();
	gets2();
	int ansb = 0;
	int s = 0;
	for (int i = 1; i <= n; i++){
		s = 0;
		if (b[i].x < s1[1].x && b[i].y < s1[1].y){
			ansb ++;
			continue;
		}
		for (int j = 1; j < top1; j++){
			s += abs(angle(s1[j + 1],s1[j],b[i]));
			if (s > are1) break;
		}
		if (s != are1) ansb ++;
	}
	ansb = n - ansb;
	int ansa = 0;
	for (int i = 1; i <= n; i++){
		s = 0;
		if (a[i].x < s2[1].x && a[i].y < s2[1].y){
			ansa ++;
			continue;
		}
		for (int j = 1; j < top2; j++){
			s += abs(angle(s2[j + 1],s2[j],a[i]));
			if (s > are2) break;
		}
		if (s != are2) ansa ++;
	}
	ansa = n - ansa;
	printf("%d %d\n",ansb,ansa);
	return 0;
}