平面上有若干条线段，有红蓝两种颜色。红色线段与XX轴平行，蓝色线段与YY 轴平行，同色线段均不相交

已知这些线段之间形成了nn个交点（在端点相交也算相交）

给出这些交点，求平面上至少有多少条线段，并输出任意一种方案。线段长度允许为00

n≤103,xi,yi≤109n \le 10^3 , x_i , y_i \le 10^9

CF 1054F

Solution

一开始在每个交点处放两条长度为00的异色线段，这显然合法

考虑通过连接相邻两个点来合并线段，每连接两个相邻点线段总数就减少11，但是显然两条异色线段可能有交

于是问题转化为，保留尽量多线段，使得它们不在除端点外相交

将线段视为点，冲突视为边，求出这个二分图的最大独立集即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 1000 + 100;
const int inf = 0x3f3f3f3f;

int N;
pii A[Maxn];

struct line
{
	int x1, y1, x2, y2;
} X[Maxn], Y[Maxn];
int cntX, cntY, ansX, ansY;

inline int cmpX (pii a, pii b) { return a.x == b.x ? (a.y < b.y) : (a.x < b.x); }
inline int cmpY (pii a, pii b) { return a.y == b.y ? (a.x < b.x) : (a.y < b.y); }

int VisX[Maxn], VisY[Maxn];

namespace Dinic
{
	const int Maxn = (1000 << 1) + 100, Maxm = Maxn * Maxn + 100;

	int e = 1, Begin[Maxn], To[Maxm << 1], Next[Maxm << 1], W[Maxm << 1];
	int Now[Maxn], Dis[Maxn];
	int S, T;

	inline void add_edge (int x, int y, int z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }

	inline void add (int x, int y, int z) { add_edge (x, y, z), add_edge (y, x, 0); }

	queue <int> Q;

	inline int bfs ()
	{
		for (int i = S; i <= T; ++i) Dis[i] = -1;
		Dis[S] = 0, Q.push (S);

		while (!Q.empty())
		{
			int x = Q.front (); Q.pop ();
			for (int i = Begin[x]; i; i = Next[i])
			{
				int y = To[i];
				if (W[i] <= 0 || Dis[y] != -1) continue;
				Dis[y] = Dis[x] + 1;
				Q.push (y);
			}
		}

		return Dis[T] != -1;
	}

	inline int dfs (int x, int now)
	{
		if (!now || x == T) return now;

		int tot = 0;
		for (int &i = Now[x]; i; i = Next[i])
		{
			int y = To[i], sum = 0;
			if (Dis[y] == Dis[x] + 1 && W[i] > 0 && (sum = dfs (y, min (W[i], now))))
			{
				W[i] -= sum, now -= sum;
				W[i ^ 1] += sum, tot += sum;
				if (!now) break;
			}
		}

		return tot;
	}

	inline void work ()
	{
		int ans = 0;

		while (bfs ())
		{
			for (int i = S; i <= T; ++i) Now[i] = Begin[i];
			ans += dfs (S, inf);
		}

		ansX = ansY = N;

		for (int i = 1; i <= cntX; ++i) if (Dis[i] != -1) VisX[i] = 1, --ansX; 
		for (int i = 1; i <= cntY; ++i) if (Dis[i + cntX] == -1) VisY[i] = 1, --ansY; 
	}

	inline void init (int _S, int _T)
	{
		S = _S, T = _T;
		for (int i = 1; i <= cntX; ++i) add (S, i, 1);
		for (int i = 1; i <= cntY; ++i) add (i + cntX, T, 1);
	}
}

inline void Init ()
{
	sort (A + 1, A + N + 1, cmpX);
	for (int i = 2; i <= N; ++i)
		if (A[i].x == A[i - 1].x)
			X[++cntX] = (line) {A[i - 1].x, A[i - 1].y, A[i].x, A[i].y};

	sort (A + 1, A + N + 1, cmpY);
	for (int i = 2; i <= N; ++i)
		if (A[i].y == A[i - 1].y)
			Y[++cntY] = (line) {A[i - 1].x, A[i - 1].y, A[i].x, A[i].y};

	Dinic :: init (0, cntX + cntY + 1);

	for (int i = 1; i <= cntX; ++i)
		for (int j = 1; j <= cntY; ++j)
			if (Y[j].x1 < X[i].x1 && X[i].x1 < Y[j].x2 && X[i].y1 < Y[j].y1 && Y[j].y1 < X[i].y2)
				Dinic :: add (i, j + cntX, 1);
}

inline void Solve ()
{
	Init ();
	Dinic :: work ();

	cout << ansY << endl;
	sort (A + 1, A + N + 1, cmpY);
	int nowY = 0, i = 1;
	while (i <= N)
	{
		int pos = i;
		while (A[pos + 1].y == A[pos].y && VisY[++nowY]) ++pos;
		printf ("%d %d %d %d\n", A[i].x, A[i].y, A[pos].x, A[pos].y);
		i = pos + 1;
	}

	cout << ansX << endl;
	sort (A + 1, A + N + 1, cmpX);
	int nowX = 0; i = 1;
	while (i <= N)
	{
		int pos = i;
		while (A[pos + 1].x == A[pos].x && VisX[++nowX]) ++pos;
		printf ("%d %d %d %d\n", A[i].x, A[i].y, A[pos].x, A[pos].y);
		i = pos + 1;
	}
}

inline void Input ()
{
	N = read<int>();
	for (int i = 1; i <= N; ++i) A[i].x = read<int>(), A[i].y = read<int>();
}

int main()
{

#ifndef ONLINE_JUDGE
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif

	Input ();
	Solve ();

	return 0;
}