Submission #677609

#TimeUsernameProblemLanguageResultExecution timeMemory
677609vjudge1Printed Circuit Board (CEOI12_circuit)C++14
5 / 100
151 ms57128 KiB
#include <bits/stdc++.h> //#include<ext/pb_ds/assoc_container.hpp> //#include<ext/pb_ds/tree_policy.hpp> using namespace std; //using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef unsigned int ui; #define ii pair<int,int> #define pll pair<ll,ll> #define vi vector<int> #define vii vector<ii> #define vll vector<ll> #define vpll vector<pll> #define matrix vector<vi> #define matrixLL vector<vll> #define vs vector<string> #define vui vector<ui> #define msi multiset<int> #define mss multiset<string> #define si set<int> #define ss set<string> #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define FOR(i, a, b) for (int i = int(a); i < int(b); i++) #define REP(i, n) FOR(i, 0, n) #define all(x) (x).begin(), (x).end() #define pld pair<ld, ld> const int dx[] = {-1, 1, 0, 0}; const int dy[] = {0, 0, -1, 1}; const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1}; const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1}; const string abc="abcdefghijklmnopqrstuvwxyz"; const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ"; const ld pi = 3.14159265; const int mod = 1e9 + 7; const int MOD = 1e9 + 7; const int MAXN = 1e6 + 7; const int inf = mod; const ll INF = 1e18; const ll zero = ll(0); const int logo = 20; const int off = 1 << logo; const int trsz = off << 1; const ld eps = 1e-10; int ccw(pll a, pll b, pll c){ ll val = a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y); if(val > 0) return 1; if(val == 0) return 0; return -1; } vpll arr; vi cv; int pos[MAXN]; matrix op; bool cmp(int ai, int bi){ pll a = arr[ai], b = arr[bi]; int cv = ccw({0, 0}, a, b); if(cv == 0) return a.X < b.X; return cv > 0; } bool cmp2(vi a, vi b){ if(pos[a[0]] == pos[b[0]]){ return pos[a[1]] < pos[b[1]]; } return pos[a[0]] < pos[b[0]]; } bool same(ld a, ld b){ if(abs(a - b) < eps) return 1; return 0; } ld dist(pll r){ return (ld)sqrt((ld)r.X * r.X + (ld)r.Y * r.Y); } //s desno od r ld dis(pld r, pld s){ if(!same(r.X, s.X) and r.X > s.X) swap(r, s); ld val = min(r.X * r.X + r.Y * r.Y, s.X * s.X + s.Y * s.Y); val = (ld)sqrt(val); if(s.X == r.X or s.Y == r.Y) return val; ld a = (ld)(s.Y - r.Y) / (ld)(s.X - r.X); if(a == 1) return val; ld b = r.Y - r.X * a; ld opx = (ld)(-b) / (ld)((ld)a + (ld)1 / (ld)a); ld opy = opx * a + b; if(opx >= min(r.X, s.X) and opx <= max(r.X, s.X) and opy >= min(r.Y, s.Y) and opy <= max(r.Y, s.Y)){ val = min(val, (ld)sqrt(opx * opx + opy * opy)); } return val; } struct cmp3{ bool operator()(ld a, ld b){ //if(abs(a - b) < eps) return 1; return a < b; } }; multiset<ld, cmp3> ud; bool bgoreq(ld a, ld b){ if(abs(a - b) < eps) return 1; return a > b; } void solve(){ int n; cin >> n; arr.resize(n); REP(i, n) cin >> arr[i].X >> arr[i].Y, cv.PB(i); sort(all(cv), cmp); REP(i, n) pos[cv[i]] = i; REP(i, n){ int nx = (i + 1) % n; int ni = i; if(pos[i] > pos[nx]) swap(ni, nx); op.PB({ni, nx, 1}); op.PB({nx, (ni + 1) * 1000, -1}); } sort(all(op), cmp2); vi sol; sol.clear(); for(auto &x : op){ if(x[2] == -1){ x[1] /= 1000; x[1]--; } ld val = dis(arr[x[0]], arr[x[1]]); if(x[2] == 1){ if(ud.empty() or bgoreq(*ud.begin(), dist(arr[x[0]]))) sol.PB(x[0] + 1); ud.insert(val); }else{ ud.erase(ud.find(val)); if(ud.empty() or bgoreq(*ud.begin(), dist(arr[x[0]]))) sol.PB(x[0] + 1); } } if(sol.empty()){ cout << 0; return; } sort(all(sol)); sol.erase(unique(all(sol)), sol.end()); cout << sol.size() << "\n"; for(auto &x : sol) cout << x << " "; cout << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t=1; //cin >> t; while(t--)solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...