比赛 |
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;
}