紫薯P230
题意：给出平面上n个白点n个黑点，要求两两配对，且配对所连线段没有交点。
紫薯思路：找出y坐标最小的点，如果多个，考虑x最小的。将其他点相对于这个点按极角从小到大排序，然后开始扫描，当白点和黑点一样多时（算上最下面的点）,第一个和最后一个匹配，然后递归匹配中间的和外边这两部分
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = + ;
int n;
struct Point
{
int x, y;
Point() {}
Point(int x, int y) : x(x), y(y) {}
double angle(const Point& p) const // 求极角
{
return atan2(y - p.y, x - p.x);
}
bool operator< (const Point& p) const // 定义 <
{
return y < p.y || (y == p.y && x < p.x);
}
void read() // 读入坐标
{
scanf("%d%d", &x, &y);
}
};
struct Node
{
Point p; // 每一个点包含x，y坐标
int id;
double ang; // 与标准点的极角
bool operator< (const Node& node) const // 定义Node的<，按极角从小到大排序
{
return ang < node.ang;
}
void getAngle(const Node& node)
{
ang = p.angle(node.p);
}
int type() // 如果是黑点（白点） 返回1,否则返回-1,判断黑点和白点数量相等时使用
{
return id <= n ? : -;
}
}p[N * ];
int ans[N * ]; // 配对表
void solve(int l, int r)
{
if (l > r)
return;
int pos = l;
for (int i = l + ; i <= r; i++)
{
if (p[i].p < p[pos].p)
pos = i;
}
swap(p[l], p[pos]); // 让怕p[l]成为最下面的点，y最小
int cnt = p[l].type();
for (int i = l + ; i <= r; i++) // 求出所有点与标准的极角大小
{
p[i].getAngle(p[l]);
}
sort(p + l + , p + r + ); // 按极角从小到大排序
for (int i = l + ; i <= r; i++)
{
cnt += p[i].type();
if (!cnt) // 黑点和白点相等时 cnt == 0
{
ans[ p[i].id ] = p[l].id; // 此时的第一个 和 最后一个配对
ans[ p[l].id ] = p[i].id;
solve(l + , i - ); // 解决内部的
solve(i + , r); // 解决外部的
return;
}
}
}
int main()
{
while (scanf("%d", &n) != EOF)
{
for (int i = ; i <= (n << ); i++)
{
p[i].p.read();
p[i].id = i;
}
solve(, n << );
for (int i = ; i <= n; i++)
{
printf("%d\n", ans[i] - n);
}
}
return ;
}