| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 4164 | gudbooy | Divide into triangle (kriii1_D) | C++98 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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()
{
int count = 0;
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();
}