/**
광활한 영토가 있다. 이 영토는 xy 평면으로 나타낼 수 있고 정확히 3N개의 말뚝이 박혀 있다. 말뚝은 서로 다른 위치에 박혀 있으며, 세 개의 말뚝이 일직선 상에 있는 경우는 없다.
N명의 사람이 영토를 나누려고 한다. 그들은 각자 3개의 말뚝을 선택하여 말뚝들을 선분으로 이었을 때 생기는 삼각형의 영역을 각자의 영토로 인정하기로 하였다. 물론 두 사람이 선택한 영토가(경계나 모서리라도) 조금이라도 겹치는 일은 일어나서는 안 된다. 그러나 조건을 만족하면서 서로의 말뚝을 선택하는 일은 똑똑하지 못한 그들에게 상당히 어려운 일이었다. 그렇기에 지나가던 똑똑한 당신에게 이 일을 맡기기로 하였다.
입력 형식
첫 번째 줄에는 사람들의 수 N (1≤N≤300)이 주어진다.
다음 3N줄에는 각 말뚝의 위치를 나타내는 두 정수 x,y (?10^6≤x,y≤10^6) 가 공백으로 구분되어 주어진다. 말뚝은 입력 받는 순서대로 1에서 3N까지의 번호가 붙는다.
출력 형식
N개의 줄에 걸쳐서 각 사람이 선택한 세 말뚝의 번호를 공백으로 구분하여 출력한다. (잘 생각해보면 알겠지만 불가능한 경우는 없다.)
**/
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
pair<pair<int,int>,int> a[1000];
int N;
void input(){
scanf("%d",&N);
for(int i=0;i<3*N;i++){
scanf("%d %d",&a[i].first.first,&a[i].first.second);
a[i].second=i+1;
}
}
void solve(){
sort(a,a+3*N);
}
void output(){
for(int i=0;i<N;i++){
printf("%d %d %d\n",a[3*i].second,a[3*i+1].second,a[3*i+2].second);
}
}
int main(){
input();
solve();
output();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 3 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 4 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 5 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 6 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 7 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 8 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 9 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 10 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 11 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 12 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 13 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 14 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 15 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 16 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 17 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 18 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 19 |
Correct |
0 ms |
1100 KB |
Output is correct |
| 20 |
Correct |
0 ms |
1100 KB |
Output is correct |
