結果
問題 |
No.2353 Guardian Dogs in Spring
|
ユーザー |
|
提出日時 | 2023-07-07 06:31:24 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,181 bytes |
コンパイル時間 | 4,799 ms |
コンパイル使用メモリ | 207,788 KB |
最終ジャッジ日時 | 2025-02-15 06:29:40 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 3 TLE * 1 -- * 36 |
ソースコード
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<bool> done(n); vector<ll> ans; for (int i = 0; i < n; i++) { std::cin >> xy[i].first >> xy[i].second; if(xy[i].first==0&&xy[i].second==0){ done[i]=true; ans.push_back(i); } } pair<ll,ll> now = {0,0}; ld last = 0; while(true){ vector<pair<ld,ll>> rem; for (int i = 0; i < n; i++) { if(done[i])continue; rem.push_back({atan2(xy[i].second-now.second,xy[i].first-now.first), i}); } if(rem.size()==0)break; sort(rem.begin(),rem.end()); auto it = lower_bound(rem.begin(),rem.end(),make_pair(last,-1ll)); if(it==rem.end())it=rem.begin(); auto [theta, ind] = *it; last = theta; done[ind]=true; 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; } }