题目链接: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);
        }
    }
}

附精美照片一枚