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