Submission #4165

#	Time	Username	Problem	Language	Result	Execution time	Memory
4165		gudbooy	Divide into triangle (kriii1_D)	C++98	0 / 1	0 ms	1696 KiB

D

#include<iostream>
#include<string.h>
#include<string>
#include<vector>
#include<iterator>
#include<algorithm>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<functional>
#include<cmath>
using namespace std;
#define MAXN 900
#define INF 987654321
int N;
int locate[MAXN][2];
double calcdis(int x1, int y1, int x2, int y2)
{
	int x, y;
	x=x1-x2;
	y=y1-y2; 
	double sum = pow(x, 2)+pow(y, 2);
	return sqrt(sum);
}
void algorithm()
{
	for(int i=0; i<(3*N); i++){
		if(locate[i][0] != INF && locate[i][1] != INF){
		vector< pair<double, int> > p;
		for(int j=i+1; j<(3*N); j++)
		{
			if(locate[j][0] != INF && locate[j][1] != INF){
			  p.push_back(make_pair(calcdis(locate[i][0], locate[i][1], locate[j][0], locate[j][1]), j));
			}
		}
			sort(p.begin(), p.end());
			int x = locate[p[0].second][0];
			int y = locate[p[0].second][1];
			locate[p[0].second][0] = locate[p[0].second][1] = INF;
			vector< pair<double, int> > p1;
		for(int j=i+1; j<(3*N); j++)
		{
			if(locate[j][0] != INF && locate[j][1] != INF){
			  p1.push_back(make_pair(calcdis(x, y, locate[j][0], locate[j][1]), j));
			}
		}	
			sort(p1.begin(), p1.end());
			cout << i+1 << " " << (p[0].second)+1 << " " << (p1[0].second)+1<<endl;
			locate[p1[0].second][0] = locate[p1[0].second][1] = INF;
			locate[i][0] = locate[i][0] = INF;
		}
	}
}
void test()
{
	cin >> N;
	for(int i=0; i<(3*N); i++)
	{
		cin >> locate[i][0] >> locate[i][1];
	}
	algorithm();
}
int main()
{
		test();		
}

• Subtask 1: 0 / 1