bzoj 1035.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#define INF 1000000000
#define eps (1e-10)
#define maxn 610
#define maxm 4010
#define pi 3.1415926535898
#define tpi 6.2831853071796
using namespace std;
struct point {
	double x,y;
	point(double x = 0,double y = 0): x(x) , y(y) {}
} dot[maxn],p[maxm << 1];
	
struct seg { point A,B,v; seg *nex; int done,sou,num; double ang; } se[maxm << 1];
struct str { seg *val; str *nex; } edge[maxm << 1];
struct poly { double s; seg *first; poly *f; int sou,pas; } land[maxm << 1];
set <int> st[maxn];
map <int,int> mp;
typedef set <int> :: iterator tm;
typedef map <int,int> :: iterator pm;

point operator + (point a,point b) { return point(a.x + b.x, a.y + b.y); }
point operator - (point a,point b) { return point(a.x - b.x, a.y - b.y); }
point operator * (point a,double b) { return point(a.x * b, a.y * b); }
double operator * (point a,point b) { return a.x * b.x + a.y * b.y; }
double operator / (point a,point b) { return a.x * b.y - a.y * b.x; }

int i,j,k,l,m,n,a,b,c,d,e,tot = 1,top,stop;
str *first[maxm << 1];
int sig(double a) {
	return (a < -eps ? -1 : (a > eps));
}

int hash(point a) {
	return (a.x * 100000 + a.y);
}

double length(point a) {
	return (sqrt(a * a));
}

void get_ang(seg &a) {
	a.ang = acos(a.v * point(1,0) / length(a.v));
	if (sig(point(1.0) / a.v) < 0) a.ang = tpi - a.ang;
}

void get_neighbor() {
	int k; seg *now = NULL; double an = -INF,just;
	for (int i = 2; i <= tot; i++) {
		an = -INF;
		k = mp.find(hash(se[i].B)) -> second;
		for (str *q = first[k]; q; q = q -> nex) {
			if (q -> val == &se[i ^ 1]) continue; 
			just = q -> val -> ang - se[i ^ 1].ang;
			if (sig(just) < 0) just += tpi;
			if (just > an) { an = just; now = q -> val; }
		}
		se[i].nex = now;
	}
}

void get_s() {
	seg *now; double al,past;
	for (int i = 2; i <= tot; i++) {
		if (se[i].done) continue;
		land[++stop].first = &se[i]; se[i].done = 1; al = 0; past = land[stop].first -> ang;
		land[stop].s = land[stop].first -> A / land[stop].first -> B;
		for (now = land[stop].first -> nex; now != land[stop].first; now = now -> nex) {
			now -> done = 1;
			land[stop].s += now -> A / now -> B;
			al += sig(now -> ang - past) > 0 ? now -> ang - past : now -> ang - past + tpi;
			past = now -> ang;
		}
		al += sig(now -> ang - past) > 0 ? now -> ang - past : now -> ang - past + tpi;
		//printf("%lf\n",al);
		land[stop].s /= 2.0;
		if (sig(land[stop].s) < 0) {
			for (now = land[stop].first -> nex; now != land[stop].first; now = now -> nex) {
				now -> done = 0;
			}
			land[stop].first -> done = 0;
			stop--;
		}
	}
}

bool cmp(poly a,poly b) { return a.s < b.s; }

bool judge(point a,poly land) {
	int ans = 0; int boo = 1;
	point A,B;
	double t; point cr;
	for (seg *k = land.first; boo || k != land.first; k = k -> nex) {
		boo = 0;
		if (!sig(point(1,0) / k -> v)) continue;
		t = (a.y - k -> A.y) / (k -> v.y);
		cr = k -> A + k -> v * t;
		A = k -> A; B = k -> B; if (A.y > B.y) swap(A,B);
		if ((sig((A.y - cr.y) * (B.y - cr.y)) <= 0) && sig(A.y - cr.y) && sig(cr.x - a.x) > 0) ans++;
	}
	return (ans & 1);
}

void find_p() {
	sort(land + 1,land + stop + 1,cmp);
	poly *ans = NULL; int mark;
	for (int i = 1; i <= stop; i++) {
		mark = 1;
		for (seg *k = land[i].first; mark || k != land[i].first; k = k -> nex) {
			mark = 0;
			land[i].pas += se[k -> num ^ 1].done ^ 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		ans = NULL;
		for (int j = 1; j <= stop; j++) {
			if (judge(dot[i],land[j])) {
				if (!ans) {
					land[j].sou = i; land[j].first -> sou = i;
					for (seg *k = land[j].first -> nex; k != land[j].first; k = k -> nex)
						k -> sou = i;
				}
				else {
					if (ans -> pas) ans -> f = &land[j];
					else break;
				}
				ans = &land[j];
			}
  		}
	}
}

int main() {
	freopen("1035.in","r",stdin);
	freopen("1035.out","w",stdout);
	scanf("%d %d",&n,&m); pm q;
	for (i = 1; i <= n; i++) {
		scanf("%lf %lf",&dot[i].x,&dot[i].y);
		//dot[i].x += 10000; dot[i].y += 10000;
	}
	for (i = 1; i <= m; i++) {
		scanf("%d %d %d %d",&a,&b,&c,&d);
		///a += 10000; b += 10000; c += 10000; d += 10000;
		k = a * 100000 + b; tot++;
		se[tot].A = point(a,b); se[tot].B = point(c,d);
		if ((q = mp.find(k)) == mp.end()) {
			mp[k] = ++top; k = top;
		}
		else k = q -> second;
		edge[++e].nex = first[k]; first[k] = &edge[e];
		edge[e].val = &se[tot]; 
		k = c * 100000 + d; tot++;
		se[tot].A = point(c,d); se[tot].B = point(a,b);
		if ((q = mp.find(k)) == mp.end()) {
			mp[k] = ++top; k = top;
		}
		else k = q -> second;
		edge[++e].nex = first[k]; first[k] = &edge[e];
		edge[e].val = &se[tot];
	}
	for (i = 2; i <= tot; i++) {
		se[i].v = se[i].B - se[i].A;
		se[i].num = i;
		get_ang(se[i]);
	}
	get_neighbor();
	get_s();
	find_p();

	for (i = 2; i <= tot; i++) {
		if (se[i].sou && se[i ^ 1].sou) st[se[i].sou].insert(se[i ^ 1].sou); 
	}

	for (i = 1; i <= stop; i++) {
		if (land[i].f) {
			if (land[i].f -> sou) st[land[i].sou].insert(land[i].f -> sou);
			if (land[i].sou) st[land[i].f -> sou].insert(land[i].sou);
		}
	}
	
	for (i = 1; i <= n; i++) {
		if (st[i].size()) {
			printf("%d ",st[i].size()); tm qn;
			for (tm q = st[i].begin(); q != st[i].end(); q++) {
				qn = q; qn++;
				if (qn != st[i].end()) printf("%d ",*q);
				else printf("%d\n",*q);
			}
		}
		else printf("0\n");
	}
	return 0;
}