【hdu 6300】Triangle Partition

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

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=6300][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);
            }
        }
    }

附精美照片一枚

![20160203175258_KVzjr.jpeg][]

[http_acm.hdu.edu.cn_showproblem.php_pid_6300]: http://acm.hdu.edu.cn/showproblem.php?pid=6300
[20160203175258_KVzjr.jpeg]: http://img4.duitang.com/uploads/item/201602/03/20160203175258_KVzjr.jpeg

发表评论取消回复

表情：

评论列表（有 0 条评论，119人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 5784 How Many Triangles（计算几何）

计算几何小知识：http://blog.csdn.net/q610376681/article/details/52215024 （包括了这里用到的计算几何知识）题目链

超、凢脫俗/ 2022年09月25日 06:29/ 0 赞/ 14 阅读

相关 LIGHTOJ-1043 -Triangle Partitioning

1043 - Triangle Partitioning <table> <tbody> <tr> <td title="special judge" st

快来打我*/ 2022年08月18日 02:38/ 0 赞/ 183 阅读

相关 Leetcode: Triangle

最近都在复习英语，看见看得头都大了，而且阅读越做分数越低！换个环境，做做Leetcode试题！题目： Given a triangle, find the minimum

拼搏现实的明天。/ 2022年08月05日 05:08/ 0 赞/ 179 阅读

相关 LeetCode-Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move t

小咪咪/ 2022年08月04日 12:42/ 0 赞/ 141 阅读

相关 TRIANGLE

var vshader_src = 'attribute vec4 a_Position;\n\ void main()

清疚/ 2022年06月18日 00:52/ 0 赞/ 175 阅读

相关 Triangle

Triangle Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/

深碍√TFBOYSˉ_/ 2022年06月10日 13:27/ 0 赞/ 179 阅读

相关 Triangles

This is a simple problem. Given two triangles A and B, you should determine they are int

你的名字/ 2022年06月09日 03:45/ 0 赞/ 187 阅读

相关 2018 HDU多校联赛第一场Triangle Partition

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

逃离我推掉我的手/ 2022年05月19日 10:05/ 0 赞/ 188 阅读

相关【hdu 6300】Triangle Partition

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

梦里梦外;/ 2022年05月18日 03:34/ 0 赞/ 120 阅读

相关 hdu多校第二场1011 （hdu6601） Keen On Everything But Triangle 主席树

题意：给定一个数列，每次询问一个区间，问这个区间中的值可组成的周长最大的三角形的周长。题解：定理1：给定一些值，这些值中组成边长最大的三角形的三条边的大小排名一定是

本是古典何须时尚/ 2021年11月11日 13:58/ 0 赞/ 221 阅读