oj.uz

Submission #349593

# Submission time Handle Problem Language Result Execution time Memory
349593 2021-01-17T22:58:48 Z CaroLinda Printed Circuit Board (CEOI12_circuit) C++14
95 / 100
 100 ms 30936 KB 
#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(' ');
 
 
}

Subtask #1
95.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 15980 KB Output is correct
2 Correct 9 ms 16108 KB Output is correct
3 Correct 10 ms 16384 KB Output is correct
4 Correct 11 ms 16384 KB Output is correct
5 Correct 14 ms 16872 KB Output is correct
6 Correct 14 ms 17020 KB Output is correct
7 Correct 20 ms 17636 KB Output is correct
8 Correct 13 ms 16688 KB Output is correct
9 Correct 14 ms 16872 KB Output is correct
10 Correct 14 ms 16872 KB Output is correct
11 Correct 14 ms 17000 KB Output is correct
12 Correct 16 ms 17636 KB Output is correct
13 Correct 25 ms 18424 KB Output is correct
14 Correct 23 ms 19168 KB Output is correct
15 Correct 25 ms 19808 KB Output is correct
16 Correct 42 ms 23516 KB Output is correct
17 Correct 74 ms 23516 KB Output is correct
18 Correct 75 ms 30936 KB Output is correct
19 Correct 78 ms 30932 KB Output is correct
20 Execution timed out 175 ms 30936 KB Time limit exceeded