比赛 |
20140418 |
评测结果 |
AWWWWWWWWW |
题目名称 |
奶牛冰壶运动 |
最终得分 |
10 |
用户昵称 |
Miku_lyt |
运行时间 |
0.187 s |
代码语言 |
C++ |
内存使用 |
1.46 MiB |
提交时间 |
2014-04-18 10:41:30 |
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct point{
int x,y;
};
point t[50050],t2[50050],t3[50050];
int s[50050];
int n;
int ans1,ans2;
int tot=0;
int top=0;
int ang(point a,point b,point c){
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
int dist(point x,point y){
return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
bool cmp(const point x,const point y){
if (ang(t[1],x,y)<0){
return 0;
}
else{
if (ang(t[1],x,y)>0){
return 1;
}
else{
return dist(t[1],x)<dist(t[1],y);
}
}
}
bool have(point x){
for (int i=1;i<=top;i++){
if (ang(x,t[s[i]],t[s[i+1]])<0){
return 0;
}
}
return 1;
}
void make(){
memset(s,0,sizeof(s));
int now=0;
int xx=0x3f3f3f3f;
int yy=0x3f3f3f3f;
for (int i=1;i<=n;i++){
if (t[i].x<xx){
xx=t[i].x;
yy=t[i].y;
now=i;
}
else{
if (t[i].x==xx&&t[i].y<yy){
yy=t[i].y;
now=i;
}
}
}
t[0]=t[1];
t[1]=t[now];
t[now]=t[0];
sort(t+2,t+n+1,cmp);
top=2;
s[1]=1;
s[2]=2;
for (int i=3;i<=n;i++){
while (top>1&&(ang(t[s[top-1]],t[s[top]],t[i])<0||(ang(t[s[top-1]],t[s[top]],t[i])==0&&dist(t[s[top-1]],t[s[top]])<=dist(t[s[top-1]],t[i])))){
top--;
}
top++;
s[top]=i;
}
s[top+1]=s[1];
tot=0;
for (int i=1;i<=n;i++){
if (have(t2[i])){
tot++;
}
}
}
int main(){
freopen("curling.in","r",stdin);
freopen("curling.out","w",stdout);
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d%d",&t[i].x,&t[i].y);
}
for (int i=1;i<=n;i++){
scanf("%d%d",&t2[i].x,&t2[i].y);
}
make();
ans1=tot;
memcpy(t3,t,sizeof(t3));
memcpy(t,t2,sizeof(t));
memcpy(t2,t3,sizeof(t2));
make();
ans2=tot;
printf("%d %d\n",ans1,ans2);
return 0;
}