2985900_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

__int64 n, m;
struct po__int64
{
	__int64 x, y;
};

po__int64 a, b, toy[5001], tmp;
__int64 num[5001];

bool cmp(po__int64 a,po__int64 b)
{
	return a.x < b.x;
}

__int64 max(double a,double b)
{
	return a > b ? a : b;
}

__int64 min(double a,double b)
{
	return a < b ? a : b;
}

__int64 multi(po__int64 p1,po__int64 p2,po__int64 p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool is__int64ersected(po__int64 s1,po__int64 e1,po__int64 s2,po__int64 e2)
{

    if(
		(max(s1.x, e1.x) >= min(s2.x, e2.x)) &&
		(max(s2.x, e2.x) >= min(s1.x, e1.x)) &&
		(max(s1.y, e1.y) >= min(s2.y, e2.y)) &&
		(max(s2.y, e2.y) >= min(s1.y, e1.y)) &&
		(multi(s2, e1, s1) * multi(e1, e2, s1) >= 0) &&
		(multi(s1, e2, s2) * multi(e2, e1, s2) >= 0)
	 )
	 return true;
	 return false;
}

__int64 b_search(po__int64 t)
{
	__int64 l, r, m;

	if(t.y > a.y || t.y < b.y || t.x < a.x || t.x > b.x)
		return -1;
	l = 0; r = n-1;
	while(l < r)
	{
		m = (l+r)/2;
		po__int64 t1, t2;
		t1.x = toy[m].x;t1.y = a.y;
		t2.x = toy[m].y;t2.y = b.y;
		if(is__int64ersected(tmp,t,t1,t2))
			l = m+(m==l);
		else
			r = m;
	}
	return l;
}

__int64 main()
{
	__int64 i, id;
	po__int64 t;
	__int64 rank[1001];

	freopen("toys.dat","r",stdin);
	freopen("ans.txt","w",stdout);
	while(scanf("%I64d",&n)==1,n)
	{
		scanf("%I64d",&m);
		memset(rank,0,sizeof(rank));
		scanf("%I64d%I64d%I64d%I64d",&a.x,&a.y,&b.x,&b.y);
		tmp.x = a.x - 1;
		tmp.y = a.y - 1;
		toy[0].x = toy[0].y = a.x;
		for(i = 1; i <= n; i++)
			scanf("%I64d%I64d",&toy[i].x,&toy[i].y);
		toy[n+1].x = toy[n+1].y = b.x;
		n = n+2;
		sort(toy,toy+n,cmp);
		memset(num,0,sizeof(num));
		for(i = 0; i < m; i++)
		{
			scanf("%I64d%I64d",&t.x,&t.y);
			id = b_search(t);
			if(id!=-1)
				num[id]++;
		}
		for(i = 1; i < n; i++)
			printf("%I64d: %I64d\n",i-1,num[i]);
		printf("\n");
	}
	return 0;
}