【HDU6300】極角排序

1.​​題目連結​​。題目大意，給3n個點，把這3n個點劃分成n個三角形。題目資料保證存在一組解。輸出每個三角形所使用的點的下标。

#include <bits/stdc++.h>
#define maxn 4005
#pragma warning(disable:4996)
typedef long long ll;
using namespace std;
const double eps = 1e-8;
struct point {
  double x, y;
  int index;
  point() {}
  point(int _x, int _y) {
    x = _x, y = _y;
  }
};
point p[maxn];
int pos;
double cross(double x1, double y1, double x2, double y2)
{
  return (x1*y2 - x2 * y1);
}

double compare(point a, point b, point c)//計算極角
{
  return cross((b.x - a.x), (b.y - a.y), (c.x - a.x), (c.y - a.y));
}
bool cmp(point a, point b)
{
  if (compare(p[pos], a, b) == 0)//計算叉積，函數在上面有介紹，如果叉積相等，按照X從小到大排序
    return a.x < b.x;
  else return compare(p[pos], a, b)> 0;
}
int main()
{
  int t;
  scanf("%d", &t);
  while (t--) 
  {
    pos = 0;
    int n;
    scanf("%d", &n);
    for (int i = 0; i < 3 * n; i++) 
    {
      scanf("%lf%lf", &p[i].x, &p[i].y);
      p[i].index = i + 1;
      if (p[0].y > p[i].y || (p[i].y == p[0].y&&p[0].x > p[i].y)) 
      {
        swap(p[i], p[0]);
      }
    }
    sort(p + 1, p + 3 * n, cmp);
    int cnt = 1;
    for (int i = 0; i < 3 * n; i++) 
    {
      if (cnt == 1) printf("%d", p[i].index);
      else printf(" %d", p[i].index);
      cnt++;
      if (cnt == 4) 
      {
        cout << endl;
        cnt = 1;
      }
    }
  }
  return 0;
}