Submission #3865

#	Time	Username	Problem	Language	Result	Execution time	Memory
3865		hyeonjae0310	Divide into triangle (kriii1_D)	C++98	0 / 1	0 ms	1240 KiB

D

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

typedef struct POINT
{
	pair<int, int> point;
	int index;
}POINT;

POINT STD;

int CCW(pair<int, int> a, pair<int, int> b, pair<int, int> c)
{
	return (a.first*b.second+b.first*c.second+c.first+a.second)-(a.second*b.first+b.second*c.first+c.second*a.first);
}

bool pair_compare(POINT a, POINT b)
{
	if(a.point.first != b.point.first)
	{
		return (a.point.first < b.point.first);
	}
	else
	{
		return (a.point.second < b.point.second);
	}
}

bool angle_compare(POINT a, POINT b)
{
	return (CCW(STD.point, a.point, b.point) > 0);
}

int main()
{
	vector<POINT> pt;
	int N;
	scanf("%d", &N);
	pt.resize(3*N);
	for(int i = 0 ; i < 3*N ; i++)
	{
		scanf("%d %d", &pt[i].point.first, &pt[i].point.second);
		pt[i].index = i+1;
	}
	sort(pt.begin(), pt.end(), pair_compare);
	STD = pt[0];
	sort(pt.begin()+1, pt.end(), angle_compare);
	for(int i = 0 ; i < 3*N ; i++)
	{
		printf("%d", pt[i].index);
		if((i+1)%3 == 0)
		{
			printf("\n");
		}
		else
		{
			printf(" ");
		}
	}
	return 0;
}

• Subtask 1: 0 / 1