Description：

给一个平面图，保证线段只在端点处相交，给出一些点的位置，问每个点和哪些点所在的区域相邻。

$1\leqslant n\leqslant 500,1\leqslant m\leqslant 4000$

Solution：

首先线段不一定联通，所以先 $dfs$ 找出每个联通块最高的点，然后做一遍扫描线求出这些最高点上面第一条线段，然后从这个点向线段的一个端点连边，这样既不影响原题的要求，也把所有线段连在了一起，然后再用最小左转法找出所有的平面，然后把每个点拿来做点定位，具体做法是扫描线求出这些点上面的第一条线段，然后就知道了每个点所在的平面，然后就直接求就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<set>

#include<cctype>

#include<cstring>

using namespace std;

int n;

struct point

{

	int x,y;

}p[4010];

namespace Pla

{

	int n;

	map<pair<int,int>,int> id;

	#define MAXM 8010

	#define fi first

	#define se second

	int pnum = 0;

	struct point

	{

		int x,y;

		pair<int,int> topair(){return make_pair(x,y);}

	}p[MAXM];

	long long operator * (point a,point b){return 1ll * a.x * b.y - 1ll * a.y * b.x;}

	struct vector

	{

		int x,y;

		double k;

		void pt(){cout << p[x].x << " " << p[x].y << " - " << p[y].x << " " << p[y].y << endl;}

	}v[MAXM << 1];

	int vnum = 0;

	void add(point a,point b)

	{

		if(id[a.topair()] == 0){id[a.topair()] = ++pnum;p[pnum] = a;}

		if(id[b.topair()] == 0){id[b.topair()] = ++pnum;p[pnum] = b;}

		v[vnum++] = (vector){id[a.topair()],id[b.topair()],atan2(b.y - a.y,b.x - a.x)};

		v[vnum++] = (vector){id[b.topair()],id[a.topair()],atan2(a.y - b.y,a.x - b.x)};

		return;

	}

	void add(int a,int b,int c,int d)

	{

		add((point){a,b},(point){c,d});

		return;

	}

	struct cmp

	{

		bool operator ()(int a,int b){return v[a].k < v[b].k;}

	};

	int tot = 0;

	set<int,cmp> s[MAXM << 1];

	int belong[MAXM << 1];

	bool vis[MAXM << 1];

	int stack[MAXM << 1],top = 0;

	void solve()

	{

		memset(belong,0,sizeof(belong));

		for(int i = 0;i < vnum;++i)

		{

			s[v[i].x].insert(i);

		}

		for(int i = 0;i < vnum;++i)

		{

			if(vis[i])continue;

			stack[top = 1] = i;vis[i] = true;

			while(true)

			{

				set<int,cmp>::iterator it = s[v[stack[top]].y].find(stack[top] ^ 1);

				++it;

				if(it == s[v[stack[top]].y].end())it = s[v[stack[top]].y].begin();

				if(vis[*it])break;

				stack[++top] = *it;

				vis[*it] = true;

			}

			long long sum = 0;

			for(int i = 1;i <= top;++i)

			{

				sum += p[v[stack[i]].x] * p[v[stack[i]].y];

			}

			if(sum > 0)continue;

			++tot;

			while(top)belong[stack[top--]] = tot;

		}

		/*for(int i = 0;i < vnum;++i)

		{

			cout << belong[i] << " : ";v[i].pt();

		}*/

	}

	int ins[MAXM << 1],cc = 0,highest[MAXM << 1];

	struct edge

	{

		int to,nxt;

	}e[MAXM << 2];

	int edgenum = 0;

	int lin[MAXM << 1] = {0};

	void add(int a,int b)

	{

		e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

		return;

	}

	bool visit[MAXM << 1];

	void dfs(int k)

	{

		visit[k] = true;

		if(highest[cc] == 0 || p[k].y > p[highest[cc]].y)

		{

			highest[cc] = k;

		}

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(visit[e[i].to])continue;

			dfs(e[i].to);

		}

		return;

	}

	void prework()

	{

		for(int i = 0;i < vnum;++i)add(v[i].x,v[i].y);

		for(int i = 1;i <= pnum;++i)

		{

			if(!visit[i])

			{

				++cc;

				dfs(i);

			}

		}

		for(int i = 0;i < vnum;++i)

		{

			belong[i] = i;

		}

		return;

	}

}

namespace Loc

{

	int n;

	#define MAXN 610

	struct point

	{

		int x,y;

	}p[MAXN];

	struct scanline

	{

		int x,id,type;

	}sc[MAXM * 3];

	int scancnt = 0;

	bool scan_cmp_x(scanline a,scanline b)

	{

		if(a.x != b.x)return a.x < b.x;

		return a.type < b.type;

	}

	struct cmp

	{

		bool operator ()(int a,int b)

		{

			int x = max(Pla::p[Pla::v[a].x].x,Pla::p[Pla::v[b].x].x);

			point ax = (point){Pla::p[Pla::v[a].x].x,Pla::p[Pla::v[a].x].y};

			point ay = (point){Pla::p[Pla::v[a].y].x,Pla::p[Pla::v[a].y].y};

			point bx = (point){Pla::p[Pla::v[b].x].x,Pla::p[Pla::v[b].x].y};

			point by = (point){Pla::p[Pla::v[b].y].x,Pla::p[Pla::v[b].y].y};

			double ya = (x - ax.x) * 1.0 * (ay.y - ax.y) / (ay.x - ax.x) + ax.y;

			double yb = (x - bx.x) * 1.0 * (by.y - bx.y) / (by.x - bx.x) + bx.y;

			bool res;

			if(fabs(ya - yb) >= 1e-4)res = (ya < yb);

			else

			{

				double sa = 1.0 * (ay.y - ax.y) / (ay.x - ax.x);

				double sb = 1.0 * (by.y - bx.y) / (by.x - bx.x);

				res = (sa < sb);

			}

			return res;

		}

	};

	set<int,cmp> s;

	int fr[MAXM << 1];

	int bel[MAXM << 1];

	void solve()

	{

		scancnt = 0;

		for(int i = 0;i < Pla::vnum;++i)

		{

			if(Pla::belong[i] == 0)continue;

			if(Pla::p[Pla::v[i].x].x >= Pla::p[Pla::v[i].y].x)continue;

			sc[++scancnt] = (scanline){Pla::p[Pla::v[i].x].x,i,0};

			sc[++scancnt] = (scanline){Pla::p[Pla::v[i].y].x,i,-1};

		}

		for(int i = 1;i <= n;++i)sc[++scancnt] = (scanline){p[i].x,i,1};

		sort(sc + 1,sc + 1 + scancnt,scan_cmp_x);

		for(int i = 1;i <= scancnt;++i)

		{

			if(sc[i].type == 0)

			{//cout << "insert " << sc[i].id << " ";Pla::v[sc[i].id].pt();

				s.insert(sc[i].id);

			}

			if(sc[i].type == -1)

			{//cout << "erase " << sc[i].id << " ";Pla::v[sc[i].id].pt();

				s.erase(sc[i].id);

			}

			if(sc[i].type == 1)

			{

				Pla::p[Pla::pnum + 1].x = p[sc[i].id].x;

				Pla::p[Pla::pnum + 1].y = p[sc[i].id].y;

				Pla::p[Pla::pnum + 2].x = p[sc[i].id].x + 1;

				Pla::p[Pla::pnum + 2].y = p[sc[i].id].y;

				Pla::v[Pla::vnum].x = Pla::pnum + 1;

				Pla::v[Pla::vnum].y = Pla::pnum + 2;

				set<int,cmp>::iterator it = s.upper_bound(Pla::vnum);

				if(it == s.end())continue;

				fr[Pla::belong[*it]] = sc[i].id;

				//cout << p[sc[i].id].x << " " << p[sc[i].id].y << " -> " << sc[i].id << " " << Pla::belong[*it] << " ";Pla::v[*it].pt();

				bel[sc[i].id] = Pla::belong[*it];

			}

		}

		s.clear();

		return;

	}

}

set<int> ss[MAXN];

int main()

{

	scanf("%d%d",&n,&Pla::n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&p[i].x,&p[i].y);

	}

	int a,b,c,d;

	for(int i = 1;i <= Pla::n;++i)

	{

		scanf("%d%d%d%d",&a,&b,&c,&d);

		Pla::add(a,b,c,d);

	}

	Pla::prework();

	for(int i = 1;i <= Pla::cc;++i)

	{

		Loc::p[i].x = Pla::p[Pla::highest[i]].x;

		Loc::p[i].y = Pla::p[Pla::highest[i]].y;

	}

	Loc::n = Pla::cc;

	Loc::solve();

	for(int i = 1;i <= Pla::cc;++i)

	{

		if(Loc::bel[i] == 0)continue;

		int p1 = Pla::v[Loc::bel[i]].x;

		Pla::add(Pla::p[p1].x,Pla::p[p1].y,Pla::p[Pla::highest[i]].x,Pla::p[Pla::highest[i]].y);

	}

	Pla::solve();

	Loc::n = n;

	for(int i = 1;i <= Loc::n;++i)

	{

		Loc::p[i].x = p[i].x;

		Loc::p[i].y = p[i].y;

	}

	memset(Loc::fr,0,sizeof(Loc::fr));

	Loc::solve();

	//for(int i = 1;i <= Loc::n;++i)cout << Loc::fr[i] << " ";cout << endl;

	for(int i = 0;i < Pla::vnum;++i)

	{

		if(Pla::belong[i] == 0 || Pla::belong[i ^ 1] == 0)continue;

		if(Loc::fr[Pla::belong[i]] == 0 || Loc::fr[Pla::belong[i]] == 0)continue;

		if(Loc::fr[Pla::belong[i]] == Loc::fr[Pla::belong[i ^ 1]])continue;

		ss[Loc::fr[Pla::belong[i]]].insert(Loc::fr[Pla::belong[i ^ 1]]);

		ss[Loc::fr[Pla::belong[i ^ 1]]].insert(Loc::fr[Pla::belong[i]]);

	}

	for(int i = 1;i <= Loc::n;++i)

	{

		printf("%d ",ss[i].size());

		for(set<int>::iterator it = ss[i].begin();it != ss[i].end();++it)printf("%d ",*it);

		puts("");

	}

	return 0;

}