2018 HDU多校联赛第一场Triangle Partition

逃离我推掉我的手 2022-05-19 10:05 171阅读 0赞

# 题目衔接：[http://acm.hdu.edu.cn/showproblem.php?pid=6300][http_acm.hdu.edu.cn_showproblem.php_pid_6300] #

# Triangle Partition #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 132768/132768 K (Java/Others)  
Total Submission(s): 636    Accepted Submission(s): 326  
Special Judge**

**Problem Description**

Chiaki has 3n points p1,p2,…,p3n. It is guaranteed that no three points are collinear.  
Chiaki would like to construct n disjoint triangles where each vertex comes from the 3n points.

**Input**

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:  
The first line contains an integer n (1≤n≤1000) -- the number of triangle to construct.  
Each of the next 3n lines contains two integers xi and yi (−109≤xi,yi≤109).  
It is guaranteed that the sum of all n does not exceed 10000.

**Output**

For each test case, output n lines contain three integers ai,bi,ci (1≤ai,bi,ci≤3n) each denoting the indices of points the i-th triangle use. If there are multiple solutions, you can output any of them.

**Sample Input**

1 1 1 2 2 3 3 5

**Sample Output**

1 2 3

**Source**

[2018 Multi-University Training Contest 1][]

题目大意：让你建造n个三角形，给出3n个点，点都是不在同一直线上的，问每个三角形，使用的点的编号是多少

思路：由于不在同一直线上，所以排个序，输出就好了

代码：

#include<map>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<vector>
    #include<cstdlib>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    const int N=1e5;
    typedef long long ll;
    struct qq
    {
        int x,y,id;
    }a[N];
    int cmp(qq A,qq B)
    {
        return A.x<B.x;
    }
    int main()
    {
       int test;
       scanf("%d",&test);
       while(test--)
       {
           int n,i,j,k;
           scanf("%d",&n);
           for(i=1;i<=3*n;i++)
           {
               scanf("%d%d",&a[i].x,&a[i].y);
               a[i].id=i;
           }
           sort(a+1,a+3*n+1,cmp);
           for(i=1;i<=3*n;i+=3)
           {
               printf("%d %d %d\n",a[i].id,a[i+1].id,a[i+2].id);
           }
       }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_6300]: http://acm.hdu.edu.cn/showproblem.php?pid=6300
[2018 Multi-University Training Contest 1]: http://acm.hdu.edu.cn/search.php?field=problem&key=2018+Multi-University+Training+Contest+1&source=1&searchmode=source