Submission #349597

#	Time	Username	Problem	Language	Result	Execution time	Memory
349597		CaroLinda	Printed Circuit Board (CEOI12_circuit)	C++14	95 / 100	177 ms	31060 KiB

circuit

#include <bits/stdc++.h>
 
template <class T = int> inline T readInt();                        
inline double readDouble();
inline int readUInt();                   
inline int readChar(); // first non-blank character
inline void readWord( char *s ); 
inline bool readLine( char *s ); // do not save '\n'
inline bool isEof();
inline int getChar(); 
inline int peekChar();
inline bool seekEof();
inline void skipBlanks();
 
template <class T> inline void writeInt( T x, char end = 0, int len = -1 );
inline void writeChar( int x ); 
inline void writeWord( const char *s );
inline void writeDouble( double x, int len = 0 );
inline void flush();
 
static struct buffer_flusher_t {
    ~buffer_flusher_t() {
        flush();
    }
} buffer_flusher;
 
/** Read */
 
static const int buf_size = 4096;
 
static unsigned char buf[buf_size];
static int buf_len = 0, buf_pos = 0;
 
inline bool isEof() {
    if (buf_pos == buf_len) {
        buf_pos = 0, buf_len = fread(buf, 1, buf_size, stdin);
        if (buf_pos == buf_len)
            return 1;
    }
    return 0;
}
 
inline int getChar() { 
    return isEof() ? -1 : buf[buf_pos++];
}
 
inline int peekChar() { 
    return isEof() ? -1 : buf[buf_pos];
}
 
inline bool seekEof() { 
    int c;
    while ((c = peekChar()) != -1 && c <= 32)
        buf_pos++;
    return c == -1;
}
 
inline void skipBlanks() {
    while (!isEof() && buf[buf_pos] <= 32U)
        buf_pos++;
}
 
inline int readChar() {
    int c = getChar();
    while (c != -1 && c <= 32)
        c = getChar();
    return c;
}
 
inline int readUInt() {
    int c = readChar(), x = 0;
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return x;
}
 
template <class T>
inline T readInt() {
    int s = 1, c = readChar();
    T x = 0;
    if (c == '-')
        s = -1, c = getChar();
    else if (c == '+')
        c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    return s == 1 ? x : -x;
}
 
inline double readDouble() {
    int s = 1, c = readChar();
    double x = 0;
    if (c == '-')
        s = -1, c = getChar();
    while ('0' <= c && c <= '9')
        x = x * 10 + c - '0', c = getChar();
    if (c == '.') {
        c = getChar();
        double coef = 1;
        while ('0' <= c && c <= '9')
            x += (c - '0') * (coef *= 1e-1), c = getChar();
    }
    return s == 1 ? x : -x;
}
 
inline void readWord( char *s ) { 
    int c = readChar();
    while (c > 32)
        *s++ = c, c = getChar();
    *s = 0;
}
 
inline bool readLine( char *s ) { 
    int c = getChar();
    while (c != '\n' && c != -1)
        *s++ = c, c = getChar();
    *s = 0;
    return c != -1;
}
 
/** Write */
 
static int write_buf_pos = 0;
static char write_buf[buf_size];
 
inline void writeChar( int x ) {
    if (write_buf_pos == buf_size)
        fwrite(write_buf, 1, buf_size, stdout), write_buf_pos = 0;
    write_buf[write_buf_pos++] = x;
}
 
inline void flush() {
    if (write_buf_pos) {
        fwrite(write_buf, 1, write_buf_pos, stdout), write_buf_pos = 0;
        fflush(stdout);
    }
}
 
template <class T> 
inline void writeInt( T x, char end, int output_len ) {
    if (x < 0)
        writeChar('-'), x = -x;
 
    char s[24];
    int n = 0;
    while (x || !n)
        s[n++] = '0' + x % 10, x /= 10;
    while (n < output_len)
        s[n++] = '0';
    while (n--)
        writeChar(s[n]);
    if (end)
        writeChar(end);
}
 
inline void writeWord( const char *s ) {
    while (*s)
        writeChar(*s++);
}
 
inline void writeDouble( double x, int output_len ) {
    if (x < 0)
        writeChar('-'), x = -x;
    int t = (int)x;
    writeInt(t), x -= t;
    writeChar('.');
    for (int i = output_len - 1; i > 0; i--) {
        x *= 10;
        t = std::min(9, (int)x);
        writeChar('0' + t), x -= t;
    }
    x *= 10;
    t = std::min(9, (int)(x + 0.5));
    writeChar('0' + t);
}
 

#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] ;
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 = readInt() ;
			 
	vector<Point> p(N) ;
	vector< pair<Point, int> > sorted ;
 
	for(int i = 0 ; i < N ; i++ ) 
	{
		p[i].x = readInt() ;
		p[i].y = readInt() ;
		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) ) ;
 
	printf("%d\n", sz(ans ) ) ;
	for(auto e : ans ) printf("%d ", e+1 ) ;
	printf("\n") ;
 
 
}

• Subtask 1: 95 / 100