Submission #3420

#	Time	Username	Problem	Language	Result	Execution time	Memory
3420		cki86201	Divide into triangle (kriii1_D)	C++98	0 / 1	4 ms	1328 KiB

D

#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
using namespace std;

struct point{
	point(){}
	point(int x,int y):x(x),y(y){}
	int x,y;
	bool operator<(const point &l)const{return x!=l.x?x<l.x:y<l.y;}
}p[920];

int N;
int ord[920];
bool check[920];
int o[920];
int u;

bool comp(const int &a,const int &b)
{
	return p[a]<p[b];
}

bool comp2(const int &a,const int &b)
{
	return atan2(p[a].y-p[u].y,p[a].x-p[u].x)<atan2(p[b].y-p[u].y,p[a].x-p[u].x);
}

void solve(int x)
{
	int i,p1=0,p2=0;
	check[x]=1;
	u=x;
	sort(ord+1,ord+1+3*N,comp2);
	for(i=1;i<=3*N;i++){
		if(check[ord[i]])continue;
		if(p1==0)p1=ord[i];
		else if(p2==0){p2=ord[i];break;}
	}
	check[p1]=check[p2]=1;
	printf("%d %d %d\n",x,p1,p2);
}

int main()
{
	int i;
	scanf("%d",&N);
	for(i=1;i<=3*N;i++){
		scanf("%d%d",&p[i].x,&p[i].y);
	}
	for(i=1;i<=3*N;i++){o[i]=i;ord[i]=i;}
	sort(o+1,o+1+3*N,comp);
	for(i=1;i<=3*N;i++){
		if(check[o[i]])continue;
		solve(o[i]);
	}
	return 0;
}

• Subtask 1: 0 / 1