Submission #3421

#	Time	Username	Problem	Language	Result	Execution time	Memory
3421		wookayin	Divide into triangle (kriii1_D)	C++98	1 / 1	0 ms	1204 KiB

D

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
 
using namespace std;
 
struct point
{
    int x,y;
        int ind;
        int use;
};
 
int n;
vector<point> dat;
 
long long ccw(const point &a, const point &b, const point &c)
{
        long long ax = b.x - a.x, ay = b.y - a.y;
        long long bx = c.x - a.x, by = c.y - a.y;
        return ax*by - bx*ay;
}
 
int main()
{
        scanf("%d",&n);
        for(int i = 0; i < 3*n;i ++) {
                int a,b;
                scanf("%d%d",&a,&b);
                point p;
                p.x = a;
                p.y = b;
                p.ind = i+1;
                p.use = 0;
                dat.push_back(p);
        }
        for(int i = 0;i < n; i++) {
                point *p1 = NULL, *p2 = NULL, *p3 = NULL;
                for(int j = 0; j < 3*n; j++) {
                        if (dat[j].use) continue;
                        if (p1 == NULL || p1->x > dat[j].x || (p1->x == dat[j].x && p1->y > dat[j].y))
                        {
                                p1 = &dat[j];
                        }
                }
                p1->use = 1;
                for(int j = 0; j < 3*n; j++) {
                        if (dat[j].use) continue;
                        if (p2 == NULL || ccw(*p1, *p2, dat[j]) > 0)
                        {
                                p2 = &dat[j];
                        }
                }
                p2->use = 1;
                for(int j = 0; j < 3*n; j++) {
                        if (dat[j].use) continue;
                        if (p3 == NULL || ccw(*p1, *p2, dat[j]) > ccw(*p1, *p2, *p3))
                        {
                                p3 = &dat[j];
                        }
                }
                p3->use = 1;
                printf("%d %d %d\n",p1->ind, p2->ind, p3->ind);
        }
        return 0;
}

• Subtask 1: 1 / 1