| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 337269 | Register | Stations (IOI20_stations) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vec;
const int N=205;
int n,ns,a[N],b[N],ans[N];
inline bool cmp1(const int&x,const int&y) {return b[x]==b[y]?a[x]<a[y]:b[x]<b[y];}
inline bool cmp2(const int&x,const int&y) {return atan2(a[x]-a[ns],b[x]-b[ns])<atan2(a[y]-a[ns],b[y]-b[ns]);}
inline void add(int x,int y) {ans[min(x,y)]=max(x,y)-n;}
void solve(vec s){
sort(s.begin(),s.end(),cmp1);
ns=s[0];s.erase(s.begin());
stable_sort(s.begin(),s.end(),cmp2);vec t;
for(int c=0,x;;){
x=s[0];s.erase(s.begin());
if((x>n)^(ns>n)) c++;else c--;
if(c>0){
add(ns,x);
if(!s.empty()) solve(s);
if(!t.empty()) solve(t);
break;
}
t.push_back(x);
}
}
signed main(){
scanf("%d",&n);vec s;
for(int i=1;i<=n*2;i++) {scanf("%d%d",&a[i],&b[i]);s.push_back(i);}
solve(s);
for(int i=1;i<=n;i++) printf("%d\n",ans[i]);
return 0;
}
//test
