結果
問題 |
No.2353 Guardian Dogs in Spring
|
ユーザー |
|
提出日時 | 2023-07-07 07:22:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,323 bytes |
コンパイル時間 | 2,192 ms |
コンパイル使用メモリ | 208,188 KB |
最終ジャッジ日時 | 2025-02-15 06:30:58 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 18 WA * 22 |
ソースコード
typedef long long ll; typedef long double ld; #include <bits/stdc++.h> using namespace std; #define int long long signed main(){ ll n; std::cin >> n; vector<pair<ll,ll>> xy(n); vector<ll> ans; set<ll> remS; for (int i = 0; i < n; i++) { std::cin >> xy[i].first >> xy[i].second; if(xy[i].first==0&&xy[i].second==0){ ans.push_back(i); }else{ remS.insert(i); } } pair<ll,ll> now = {0,0}; ld last = 0; while(remS.size()>0){ set<pair<ld,ll>> rem; pair<ll,ll> L = {1e18,-1}; pair<ll,ll> mi = {1e18,-1}; for (auto i : remS) { ld t = atan2(xy[i].second-now.second,xy[i].first-now.first); if(t>last&&t<L.first){ L.first = t; L.second =i; } if(mi.first>t){ mi.first = t; mi.second = i; } } ld theta = L.second==-1 ? mi.first : L.first; ll ind = L.second==-1 ? mi.second : L.second; last = theta; remS.erase(ind); now = xy[ind]; ans.push_back(ind); } std::cout << ans.size()/2 << std::endl; for (int i = 0; i < ans.size()/2; i++) { std::cout << ans[2*i]+1<<" "<<ans[2*i+1]+1 << std::endl; } }