【hdu 6300】Triangle Partition-蒲公英云

【hdu 6300】Triangle Partition

梦里梦外; 2022-05-18 03:34 203阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6300

题意：有T组测试样列，输入的n代表要组成的三角形的个数，接下来3n行代表3n个点，输出n行，每行输出组成三角形的点的序号。

思路：因为题上说保证没有3个点共线，因此只需要将所有点按x和y进行从小到大排序，然后3个点一个三角形。（但这道题我用运算符重载排序时，wa了，提示我时间超限，改成cmp后却过咧 Ծ‸Ծ ）

My DaiMa：

#include<bits/stdc++.h>
//#include<set>
using namespace std;
const int Max = 1e5+5;
struct triangle
{
    int x,y,k;
};
triangle t[Max];
int cmp(triangle t1,triangle t2)
{
    if(t1.x == t2.x)
        return t1.y < t2.y;
    return t1.x < t2.x;
}
int main()
{
    int T,n;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i = 0; i < 3*n; i++)
        {
            scanf("%d%d",&t[i].x,&t[i].y);
            t[i].k = i+1;
        }
        sort(t,t+3*n,cmp);//将所有点从小到大排序
        for(int i = 0; i < 3*n ; i++)
        {
            if((i+1)%3 == 0)
                printf("%d\n",t[i].k);//输出点的序号
            else
                printf("%d ",t[i].k);
        }
    }
}