比赛 |
20140418 |
评测结果 |
ATTTTTTTTW |
题目名称 |
奶牛冰壶运动 |
最终得分 |
10 |
用户昵称 |
HZOI_lhy111 |
运行时间 |
8.003 s |
代码语言 |
C++ |
内存使用 |
1.84 MiB |
提交时间 |
2014-04-18 11:25:31 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
int ax1[50010],ay1[50010],bx1[50010],by1[50010],ax2[50010],ay2[50010],bx2[50010],by2[50010];
int n,ans_a,ans_b;
inline void swap(int &a,int &b)
{
a ^= b;
b = a ^ b;
a ^= b;
}
inline bool cross_a(int a_num,int l,int r,int h)
{
int vec_x = ax1[a_num] - bx1[l] + ax1[a_num] - bx1[r];
int vec_y = ay1[a_num] - by1[l] + ay1[a_num] - by1[r];
int vec1_x = ax1[a_num] - bx2[h];
int vec1_y = ay1[a_num] - by2[h];
if (vec_x * (long long)vec1_x + vec_y * (long long)vec1_y <= 0)
return true;
else
return false;
}
inline bool cross_a1(int a_num,int l,int r,int h)
{
int vec_x = ax1[a_num] - bx2[l] + ax1[a_num] - bx2[r];
int vec_y = ay1[a_num] - by2[l] + ay1[a_num] - by2[r];
int vec1_x = ax1[a_num] - bx1[h];
int vec1_y = ay1[a_num] - by1[h];
if (vec_x * (long long)vec1_x + vec_y * (long long)vec1_y <= 0)
return true;
else
return false;
}
inline bool cross_b(int b_num,int l,int r,int h)
{
int vec_x = bx1[b_num] - ax1[l] + bx1[b_num] - ax1[r];
int vec_y = by1[b_num] - ay1[l] + by1[b_num] - ay1[r];
int vec1_x = bx1[b_num] - ax2[h];
int vec1_y = by1[b_num] - ay2[h];
if (vec_x * (long long)vec1_x + vec_y * (long long)vec1_y <= 0)
return true;
else
return false;
}
inline bool cross_b1(int b_num,int l,int r,int h)
{
int vec_x = bx1[b_num] - ax2[l] + bx1[b_num] - ax2[r];
int vec_y = by1[b_num] - ay2[l] + by1[b_num] - ay2[r];
int vec1_x = bx1[b_num] - ax1[h];
int vec1_y = by1[b_num] - ay1[h];
if (vec_x * (long long)vec1_x + vec_y * (long long)vec1_y <= 0)
return true;
else
return false;
}
inline void qsort_a1(int l,int r)
{
int i = l;
int j = r;
int mivx = ax1[(i+j)>>1];
int mivy = ay1[(i+j)>>1];
do
{
while ((ax1[i] < mivx) || (ax1[i] == mivx && ay1[i] < mivy)) i++;
while ((ax1[j] > mivx) || (ax1[j] == mivx && ay1[j] > mivy)) j--;
if (i <= j)
{
if (ax1[i] != ax1[j])
swap(ax1[i],ax1[j]);
if (ay1[i] != ay1[j])
swap(ay1[i],ay1[j]);
i++;
j--;
}
}while (i <= j);
if (i < r) qsort_a1(i,r);
if (l < j) qsort_a1(l,j);
}
inline void qsort_b1(int l,int r)
{
int i = l;
int j = r;
int mivx = bx1[(i+j)>>1];
int mivy = by1[(i+j)>>1];
do
{
while ((bx1[i] < mivx) || (bx1[i] == mivx && by1[i] < mivy)) i++;
while ((bx1[j] > mivx) || (bx1[j] == mivx && by1[j] > mivy)) j--;
if (i <= j)
{
if (bx1[i] != bx1[j])
swap(bx1[i],bx1[j]);
if (by1[i] != by1[j])
swap(by1[i],by1[j]);
i++;
j--;
}
}while (i <= j);
if (i < r) qsort_b1(i,r);
if (l < j) qsort_b1(l,j);
}
inline void qsort_a2(int l,int r)
{
int i = l;
int j = r;
int mivx = ax2[(i+j)>>1];
int mivy = ay2[(i+j)>>1];
do
{
while ((ay2[i] > mivy) || (ay2[i] == mivy && ax1[i] < mivx)) i++;
while ((ay2[j] < mivy) || (ay2[j] == mivy && ax2[j] > mivx)) j--;
if (i <= j)
{
if (ax2[i] != ax2[j])
swap(ax2[i],ax2[j]);
if (ay2[i] != ay2[j])
swap(ay2[i],ay2[j]);
i++;
j--;
}
}while (i <= j);
if (i < r) qsort_a2(i,r);
if (l < j) qsort_a2(l,j);
}
inline void qsort_b2(int l,int r)
{
int i = l;
int j = r;
int mivx = bx2[(i+j)>>1];
int mivy = by2[(i+j)>>1];
do
{
while ((by2[i] > mivy) || (by2[i] == mivy && bx1[i] < mivx)) i++;
while ((by2[j] < mivy) || (by2[j] == mivy && bx2[j] > mivx)) j--;
if (i <= j)
{
if (bx2[i] != bx2[j])
swap(bx2[i],bx2[j]);
if (by2[i] != by2[j])
swap(by2[i],by2[j]);
i++;
j--;
}
}while (i <= j);
if (i < r) qsort_b2(i,r);
if (l < j) qsort_b2(l,j);
}
inline bool check_a(int x)
{
int l = 0,r = 0,h;
for (int i = 1;i <= n;i++)
if (by1[i] < ay1[x])
{
l = i;
break;
}
for (int i = n;i >= 1;i--)
if (by1[i] < ay1[x])
{
r = i;
break;
}
if (l == r)
{
h = l;
l = 0;
r = 0;
for (int i = 1;i <= n;i++)
if (by2[i] > ay1[x])
{
l = i;
break;
}
if (l == 0) return false;
for (int i = n;i >= 1;i--)
if (by2[i] > ay1[x])
{
r = i;
break;
}
if (l == r) return false;
if (cross_a1(x,l,r,h)) return true;
return false;
}
else
for (int i = 1;i <= n;i++)
{
if (by2[i] < ay1[x]) break;
if (cross_a(x,l,r,i)) return true;
}
return false;
}
inline bool check_b(int x)
{
int l = 0,r = 0,h;
for (int i = 1;i <= n;i++)
if (ay1[i] < by1[x])
{
l = i;
break;
}
for (int i = n;i >= 1;i--)
if (ay1[i] < by1[x])
{
r = i;
break;
}
if (l == r)
{
h = l;
l = 0;
r = 0;
for (int i = 1;i <= n;i++)
if (ay2[i] > by1[x])
{
l = i;
break;
}
if (l == 0) return false;
for (int i = n;i >= 1;i--)
if (ay2[i] > by1[x])
{
r = i;
break;
}
if (l == r) return false;
if (cross_b1(x,l,r,h)) return true;
return false;
}
else
for (int i = 1;i <= n;i++)
{
if (ay2[i] < by1[x]) break;
if (cross_b(x,l,r,i)) return true;
}
return false;
}
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",&ax1[i],&ay1[i]);
ax2[i] = ax1[i];
ay2[i] = ay1[i];
}
for (int i = 1;i <= n;i++)
{
scanf("%d%d",&bx1[i],&by1[i]);
bx2[i] = bx1[i];
by2[i] = by1[i];
}
qsort_a1(1,n);
qsort_a2(1,n);
qsort_b1(1,n);
qsort_b2(1,n);
ans_a = 0;
ans_b = 0;
for (int i = 1;i <= n;i++)
if (check_a(i)) ans_b++;
for (int i = 1;i <= n;i++)
if (check_b(i)) ans_a++;
printf("%d %d\n",ans_a,ans_b);
return 0;
}