Submission #349593

#TimeUsernameProblemLanguageResultExecution timeMemory
349593CaroLindaPrinted Circuit Board (CEOI12_circuit)C++14
95 / 100
175 ms30936 KiB
#include <bits/stdc++.h> #define sz(x) (int)(x.size()) #define debug printf #define lp(i,a,b) for(int i = a ; i < b; i++) #define pb push_back #define ff first #define ss second #define mk make_pair #define pii pair<int,int> #define ll long long #define all(x) x.begin(),x.end() const int MAX = 2e5+5 ; using namespace std ; int in() { char c=0; while(c<'0'||c>'9') c=getchar(); int r=0; while(c>='0'&&c<='9') { r=r*10+c-'0'; c=getchar(); } return r; } void out(int x) { int c=0, r=0; for(; x%10==0; ++c, x/=10); for(; x; r=r*10+x%10, x/=10); for(; r; r/=10) putchar('0'+r%10); while(c--) putchar('0'); } int N ; int myId[MAX] ; double num[MAX], den[MAX] ; bool canceled[MAX] ; struct Point { ll x , y ; Point(ll x=0, ll y=0):x(x), y(y) {} bool operator == ( Point other ) const { return x == other.x && y == other.y ; } bool operator != (Point other ) const { return x != other.x || y != other.y ; } Point operator - (Point other) const { return Point(x-other.x, y-other.y) ; } ll operator % (Point other) const { return x*other.y - y*other.x ; } ll operator *(Point other) const { return x*other.x + y*other.y ; } void read() { scanf("%lld %lld", &x, &y) ; } } ; struct Line { Point p1, p2 ; double cte ; Line( Point p1 = Point(0,0) , Point p2 = Point(0,0) ) : p1(p1) , p2(p2) {} } t ; double dx , dy ; double num1, num2, den1, den2 , auxDx ,auxDy ; struct Seg { Line tree[MAX*2] ; int n ; int l[MAX*2], r[MAX*2] ; void ini() { for(int i= n ; i < 2*n ; i++ ) l[i] = r[i] = i - n ; for(int i= n-1 , lef, rig ; i > 0 ; i-- ) { lef = i<<1 , rig = i<<1|1 ; l[i] = ( l[lef] < l[rig] ) ? l[lef] : l[rig] ; r[i] = ( r[lef] > r[rig] ) ? r[lef] : r[rig] ; } } void upd(int pos ) { if( tree[pos].p1 == Point(0,0) ) return (void)(tree[pos] = t ) ; auxDx = (tree[pos].p1.x - tree[pos].p2.x ) ; auxDy = (tree[pos].p1.y - tree[pos].p2.y ) ; for(auto e : {l[pos] , r[pos] } ) { num1 = den[e] * tree[pos].cte ; den1 = den[e] * auxDy - num[e] * auxDx ; num2 = den[e] * t.cte ; den2 = den[e] * dy - num[e] * dx ; if( tree[pos].p1.x == tree[pos].p2.x ) num1 = tree[pos].p1.x, den1 = 1LL ; if(t.p1.x == t.p2.x ) num2 = t.p1.x , den2 = 1LL ; if( (num1/den1) < (num2/den2) ) return ; } tree[pos] = t ; } void addLine(int l, int r ) { dy = ( t.p1.y - t.p2.y ) ; dx = (t.p1.x-t.p2.x ) ; for( l += n , r += n ; l < r ; l >>= 1 , r >>= 1 ) { if(l&1) { upd(l) ; l++ ; } if(r&1) upd(--r) ; } } bool qry(int pos, Point p ) { for(pos += n ; pos > 0 ; pos >>= 1 ) { if( tree[pos].p1 == Point(0,0) || tree[pos].p1 == p || tree[pos].p2 == p ) continue ; ll val1 = (tree[pos].p2 - tree[pos].p1)%(p-tree[pos].p1) ; ll val2 = (tree[pos].p2-tree[pos].p1)%(Point(0,0)-tree[pos].p1 ) ; if( (val1 < 0 ) != (val2 < 0) ) return false ; } return true ; } } seg ; int main() { N = in() ; vector<Point> p(N) ; vector< pair<Point, int> > sorted ; for(int i = 0 ; i < N ; i++ ) { p[i].x = in() ; p[i].y = in() ; sorted.push_back( make_pair(p[i], i ) ) ; } sort(all(sorted), [&]( pair<Point,int> a, pair<Point,int> b ) { if( a.first%b.first == 0 ) return (b.first-a.first)*(Point(0,0)-a.first ) < 0 ; return a.first%b.first > 0 ; } ) ; int j = -1 ; for(int i = 0 ; i < N ; i++ ) { if(!i || sorted[i-1].first%sorted[i].first != 0 ) j++ ; else { canceled[ sorted[i].second ] = true ; myId[ sorted[i].second ] = j ; continue ; } myId[sorted[i].second ] = j ; num[j] = sorted[i].first.y ; den[j] = sorted[i].first.x ; } seg.n = j+1 ; seg.ini() ; for(int i = 0 , nxt = 1 ; i < N ; i++, nxt++ ) { if(nxt == N ) nxt = 0 ; int l = myId[i] , r = myId[nxt] ; if(l == r ) continue ; if( l > r ) swap(l,r) ; t.p1 = p[i] ; t.p2 = p[nxt] ; t.cte = ( t.p1.y*t.p2.x - t.p1.x*t.p2.y ) ; seg.addLine(l,r+1 ) ; } //Don't forget to check if there is someone in the same polar angle that mine (because, if there is, it fucks everything up ) vector<int> ans ; int x = sorted[0].second ; int nxt = x+1 ; int ant = x-1 ; if(nxt == N ) nxt = 0 ; if(ant == -1 ) ant = N-1 ; int toAdd = 1 ; if( (p[nxt]-p[x] ) % (p[ant]-p[x]) > 0 ) toAdd = -1 ; while(true) { if( !canceled[x] && seg.qry(myId[x], p[x] ) ) ans.push_back(x) ; if( p[x].x == den[j] && p[x].y == num[j] ) break ; x += toAdd ; if(x == N ) x = 0 ; if( x == -1 ) x = N-1 ; } sort(all(ans) ) ; out(sz(ans) ) ; putchar('\n'); for(auto e : ans ) out(e+1) , putchar(' '); }
#Verdict Execution timeMemoryGrader output
Fetching results...