Submission #3632

#	Time	Username	Problem	Language	Result	Execution time	Memory
3632		eldkqmfhf123	Divide into triangle (kriii1_D)	C++98	0 / 1	0 ms	2404 KiB

D

#include<iostream>
#include<math.h>
#include<algorithm>
#define oo 0x7fffffff

using namespace std;


double Dist[301][301];

double dist(int ax,int ay, int bx, int by)
{
	double a = (bx-ax)*(bx-ax);
	double b = (by-ay)*(by-ay);
	return sqrt(a+b);
}
int Data[901][2];
int visit[901];
int main()
{
	int n;
	cin >> n;
	int i,j;
	for(i=0;i<3*n;i++)
		cin >> Data[i][0] >> Data[i][1];

	n *= 3;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			Dist[i][j] = dist(Data[i][0],Data[i][1],Data[j][0],Data[j][1]);
		}
	}

	for(int t=0;t<n/3;t++)
	{
		for(i=0;i<n;i++)
		{
			if(visit[i])continue;
			double MIN = oo;
			int MINJ;
			for(j=0;j<n;j++)
			{
				if(visit[j])continue;
				if(i==j)continue;
				if(MIN > Dist[i][j])
				{
					MIN = Dist[i][j];
					MINJ = j;
				}
			}
			double MIN2 = oo;
			int MINJ2;
			for(j=0;j<n;j++)
			{
				if(visit[j])continue;
				if(i==j || MINJ == j)continue;
				if(MIN2 > Dist[i][j])
				{
					MIN2 = Dist[i][j];
					MINJ2 = j;
				}
			}

			int tmp[4];
			tmp[0]=i+1;
			tmp[1]=MINJ+1;
			tmp[2]=MINJ2+1;
			for(int q=0;q<3;q++)
				cout << tmp[q] << " ";
			cout << endl;
			sort(tmp,tmp+3);
			visit[i]=1;
			visit[MINJ]=1;
			visit[MINJ2]=1;
			break;
		}
	}
	return 0;
}

• Subtask 1: 0 / 1