2882872_ac_15ms_80k.cpp

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

#include <algorithm>

using namespace std;

struct point
{
	double x, y;
};

struct segment
{
	double l, r;
};

struct line
{
	double a, b, c;
};

line LineFromSeg(point a,point b)
{
	line l;

	l.a = b.y - a.y;
    l.b = a.x - b.x;
    l.c = b.x * a.y - a.x * b.y;
	return l;
}

bool cmp(segment a,segment b)
{
	return a.l < b.l;
}

int main()
{
	int i, j, n, cas, no;
	point a, b, light;
	line l;
	segment seg[200];
	double left, right, tmp;
	int num;

	scanf("%d",&cas);
	while(cas--)
	{
		scanf("%d",&n);
		no = 0;num = 0;
		scanf("%lf%lf",&light.x,&light.y);
		for(i = 0; i < n; i++)
		{
			scanf("%lf%lf%lf%lf",&a.x,&a.y,&b.x,&b.y);
			l = LineFromSeg(a,light);
			seg[no].l = -l.c/l.a;
			l = LineFromSeg(b,light);
			seg[no].r = -l.c/l.a;
			if(seg[no].l-seg[no].r>=0)
			{
				tmp = seg[no].l;
				seg[no].l = seg[no].r;
				seg[no].r = tmp;
			}
			no++;
		}
		sort(seg,seg+no,cmp);
		for(i = 0; i < no; i++)
		{
			left = seg[i].l,right = seg[i].r;
			j = i;
			while(j<no&&seg[j].l<=right)
			{
				if(seg[j].r>right)
					right = seg[j].r;
				j++;
			}
			num++;
			i = j-1;
		}
		printf("%d\n",num+1);
	}
	return 0;
}