【题目大意】
给你$n$个点，被一个半径为$R$的元圆划分成内（包含边界）、外两个部分。
要连若干线，每个点只能连一条线，不存在重点和三点共线。
线只能连在内部点和外部点之间，线长度不超过$d$。
如果一个外部点$w$和三个内部点$x,y,z$距离都不超过$d$，且两个内部点$x,z$没有和外部点$w$连线，我们准备从外部点$w$连到内部点$y$。那么如果$x$和$z$的连线有和$w$和$y$的连线相交，那么是不合法的。
求合法情况下，最多连多少线。以及方案。
$1 leq n leq 10^3, 1 leq |x_i|, |y_i|, d, R leq 2 imes 10^4$
【题解】
考虑先把点分类。很明显发现答案=最大匹配。
对于每个外部点，以它为中心把内部点极角排序，那么得到了一个访问序列，然后我们直接跑匈牙利即可。
考虑这样如何保证那个奇怪的条件：
如果$x,y,z$按极角序顺次排过来，那么扫到$y$的时候，$x$如果没被匹配，一定先被扫描了，并当做匹配点。
所以这样保证了没有奇怪的条件这个情况。
然后我们就能求出匹配，考虑求方案。
对于匹配，需要找到一个合法的连边顺序（就保证一定要按这个极角序从前往后连边即可）
暴力找方案即可。
总复杂度$O(n^3)$，匈牙利跑不满，而且n一般来说为n/2（因为把点分成了一半）
这里极角排序可以用叉积，因为是圆外的点朝圆内的点连边，角度范围小于180°。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef long double ld; const int M = 1010, N = 1e5 + 10; const int mod = 998244353; int n, R, d; struct P { int x, y; P() {} P(int x, int y) : x(x), y(y) {} friend P operator + (P a, P b) { return P(a.x + b.x, a.y + b.y); } friend P operator - (P a, P b) { return P(a.x - b.x, a.y - b.y); } friend int operator * (P a, P b) { return a.x * b.y - a.y * b.x; } }a[M], b[M], C; int an, bn; struct pa { P a; int id; pa() {} pa(P a, int id) : a(a), id(id) {} }c[M]; int cn; P cmp_t; int g[M][M], gn[M]; inline bool cmp(pa a, pa b) { return (a.a - cmp_t) * (b.a - cmp_t) > 0; } inline ll dis2(P a, P b) { return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); } bool vis[M]; int from[M], to[M]; int aid[M], bid[M]; inline int hungry(int x) { for (int i=1; i<=gn[x]; ++i) { if(!vis[g[x][i]]) { vis[g[x][i]] = 1; if(from[g[x][i]] == 0 || hungry(from[g[x][i]])) { from[g[x][i]] = x; return 1; } } } return 0; } int main() { freopen("etoile.in", "r", stdin); freopen("etoile.out", "w", stdout); cin >> n >> R >> d; for (int i=1, _x, _y; i<=n; ++i) { scanf("%d%d", &_x, &_y); if(i == 1) C = P(_x, _y); if(dis2(P(_x, _y), C) <= (ll)R * R) aid[++an] = i, a[an] = P(_x, _y); else bid[++bn] = i, b[bn] = P(_x, _y); } // puts("==========="); // for (int i=1; i<=an; ++i) printf("%d %d ", a[i].x, a[i].y); // puts("==========="); // for (int i=1; i<=bn; ++i) printf("%d %d ", b[i].x, b[i].y); // puts("==========="); for (int i=1; i<=bn; ++i) { cmp_t = b[i]; cn = 0; for (int j=1; j<=an; ++j) if(dis2(a[j], cmp_t) <= (ll)d * d) c[++cn] = pa(a[j], j); sort(c+1, c+cn+1, cmp); for (int j=1; j<=cn; ++j) g[i][j] = c[j].id; gn[i] = cn; } int ans = 0; for (int i=1; i<=bn; ++i) { memset(vis, 0, sizeof vis); ans += hungry(i); } for (int i=1; i<=an; ++i) to[from[i]] = i; memset(vis, 0, sizeof vis); cout << (ans << 1) << endl; for (int i=1; i<=ans; ++i) { bool hv = 0; for (int j=1; j<=bn; ++j) { if(!to[j]) continue; for (int k=1; k<=gn[j]; ++k) { if(!vis[g[j][k]]) { if(g[j][k] == to[j]) hv = 1; break; } } if(hv) { vis[to[j]] = 1; printf("%d %d ", bid[j], aid[to[j]]); break; } } } return 0; } /* 10 5530 5385 8 5730 5220 61 2896 2950 1025 649 5509 1773 6057 2432 6435 975 5366 8341 1127 3616 2849 1689 */