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