题意： n个A类点，n个B类点。 要求对于每个A类点连一个折线到一个B类点，折线间不相交。
思路： 因为所有点的x轴坐标和y轴坐标不同，所以直接相邻两个不同种类的点，直接在下边界会和，然后每次扩大下边界。
#include <cstdio> #include <cassert> #include <cmath> #include <vector> #include <cstring> #include <algorithm> using namespace std; typedef long long ll; struct Node { int x,y,id; }a[1005]; int cmp(Node a,Node b) { return a.x < b.x; } int main() { int T;scanf("%d",&T); while(T--) { int n;scanf("%d",&n); for(int i = 1;i <= n;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].id = 1; } for(int i = 1;i <= n;i++) { scanf("%d%d",&a[i + n].x,&a[i + n].y); a[i + n].id = 2; } int down = -500; vector<Node>vec; for(int i = 1;i <= n;i++) { sort(a + 1,a + 1 + n * 2,cmp); for(int j = 1;j <= n * 2;j ++) { if(a[j].x > 1000) break; if(a[j].id != a[j + 1].id) { printf("%d\n",4); printf("%d %d\n",a[j].x,a[j].y); printf("%d %d\n",a[j].x,down); printf("%d %d\n",a[j + 1].x,down); printf("%d %d\n",a[j + 1].x,a[j + 1].y); a[j].x = a[j + 1].x = 2000; break; } } down -= 2; } } return 0; }