oj.uz

Submission #349583

# Submission time Handle Problem Language Result Execution time Memory
349583 2021-01-17T21:23:03 Z CaroLinda Printed Circuit Board (CEOI12_circuit) C++11
90 / 100
 100 ms 30928 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma") 
#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 ;
 
char c ;
void readInt(int &num)
{
	num = 0 ;
	for(c = getchar() ; (c > 47 && c <58 ) ; c = getchar() )
		num = num*10 + c - 48 ;
}
 
void readLong(ll &num ) 
{
	num = 0 ;
	for(c = getchar() ; (c> 47 && c < 58 ) ; c = getchar() )
		num = num*10 + c - 48 ;
}
 
int N ;
int myId[MAX] ;
double num[MAX], den[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 ; i > 0 ; i-- )
		{
			l[i] = min(l[i<<1], l[i<<1|1] ) ;
			r[i] = max(r[i<<1], r[i<<1|1] ) ;
		}
 
	}
 
	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()
{
 
	readInt(N) ;
		 
	vector<Point> p(N) ;
	vector< pair<Point, int> > sorted ;
 
	for(int i = 0 ; i < N ; i++ ) 
	{
		readLong(p[i].x ) ;
		readLong(p[i].y ) ;
		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++ ;
	   		
		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 ;
	for(int i=0 ; i < N ; i++ )
	{
		if(i && sorted[i-1].first%sorted[i].first == 0 ) continue ;
		if(seg.qry(myId[ sorted[i].second ] , sorted[i].first ) ) ans.push_back(sorted[i].second ) ;
	}
 
	sort(all(ans) ) ;
 
	printf("%d\n", sz(ans ) ) ;
	for(auto e : ans ) printf("%d ", e+1 ) ;
	printf("\n") ;
 
 
}

Subtask #1
90.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 15980 KB Output is correct
2 Correct 11 ms 16108 KB Output is correct
3 Correct 12 ms 16364 KB Output is correct
4 Correct 13 ms 16364 KB Output is correct
5 Correct 16 ms 16872 KB Output is correct
6 Correct 16 ms 16872 KB Output is correct
7 Correct 22 ms 17636 KB Output is correct
8 Correct 15 ms 16688 KB Output is correct
9 Correct 15 ms 16744 KB Output is correct
10 Correct 16 ms 16872 KB Output is correct
11 Correct 17 ms 17000 KB Output is correct
12 Correct 19 ms 17636 KB Output is correct
13 Correct 29 ms 18404 KB Output is correct
14 Correct 29 ms 19040 KB Output is correct
15 Correct 32 ms 19808 KB Output is correct
16 Correct 54 ms 23516 KB Output is correct
17 Correct 84 ms 23516 KB Output is correct
18 Execution timed out 102 ms 30928 KB Time limit exceeded
19 Correct 100 ms 30928 KB Output is correct
20 Execution timed out 181 ms 30928 KB Time limit exceeded