比赛 |
20140418 |
评测结果 |
AWWWWWWWWW |
题目名称 |
奶牛冰壶运动 |
最终得分 |
10 |
用户昵称 |
ys |
运行时间 |
0.203 s |
代码语言 |
C++ |
内存使用 |
1.91 MiB |
提交时间 |
2014-04-18 09:19:20 |
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n;
struct node{
int x,y;
};
node a[50005],b[50005],s[100005];
int 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++)
scanf("%d%d",&a[i].x,&a[i].y);
for (int i=1;i<=n;i++)
scanf("%d%d",&b[i].x,&b[i].y);
sort(a+1,a+n+1,cmp);
sort(b+1,b+n+1,cmp);
}
int 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(){
ans1=ans2=0;
Tubao1();
Tubao2();
printf("%d %d\n",ans1,ans2);
}
int main(){
freopen("curling.in","r",stdin);
freopen("curling.out","w",stdout);
init();
solve();
return 0;
}