2985914_ac_312ms_184k.cpp

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

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

using namespace std;

int n, m;
struct point
{
	__int64 x, y;
};

point a, b, toy[5001], tmp;
int num[5001];

bool cmp(point a,point 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(point p1,point p2,point p0)
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool is__int64ersected(point s1,point e1,point s2,point 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;
}

int b_search(point t)
{
	int 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;
		point 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;
}

int main()
{
	int i, id;
	point t;

	while(scanf("%d",&n)==1,n)
	{
		scanf("%d",&m);
		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("%d: %d\n",i-1,num[i]);
		printf("\n");
	}
	return 0;
}