| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 349592 | CaroLinda | Printed Circuit Board (CEOI12_circuit) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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_unlocked();
int r=0;
while(c>='0'&&c<='9') {
r=r*10+c-'0';
c=getchar_unlocked();
}
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_unlocked('0'+r%10);
while(c--)
putchar_unlocked('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) ;
a#include <bits/stdc++.h>
using namespace std;
int in() {
char c=0;
while(c<'0'||c>'9')
c=getchar_unlocked();
int r=0;
while(c>='0'&&c<='9') {
r=r*10+c-'0';
c=getchar_unlocked();
}
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_unlocked('0'+r%10);
while(c--)
putchar_unlocked('0');
}
const int mxN=2e5;
int n, l, r;
long long x[mxN+1], y[mxN+1];
vector<int> v, s;
bool b[mxN];
int main() {
auto cp=[](int a, int b, int c) {
return (y[c]-y[a])*(x[b]-x[a])-(y[b]-y[a])*(x[c]-x[a]);
};
n=in();
for(int i=0; i<n; ++i) {
x[i]=in(), y[i]=in();
if(!i||cp(n, l, i)>0||!cp(n, l, i)&&x[i]<x[l])
l=i;
if(!i||cp(n, r, i)<0||!cp(n, r, i)&&x[i]<x[r])
r=i;
}
int ic=cp((l+n-1)%n, l, (l+1)%n)>0?1:n-1;
for(; l^r; l=(l+ic)%n)
v.push_back(l);
v.push_back(r);
s={0, 1};
for(int i=2; i<v.size(); ++i) {
auto ul=[&]() {
while(cp(n, v[s.back()], v[i])>=0&&cp(v[i-1], v[i], v[s.back()])<=0)
s.pop_back();
for(int j=i, c=cp(n, v[s.back()], v[i])<0; cp(n, v[s.back()], v[i])>=0||!c; ++i) {
if(i^j?cp(n, v[j], v[i])>=0&&cp(n, v[j], v[i+1])<0&&cp(v[i], v[i+1], v[j])>0:cp(n, v[i], v[i+1])<0&&cp(v[i-1], v[i], v[i+1])>0)
++c;
if(cp(n, v[j], v[i])<0&&cp(n, v[j], v[i+1])>=0&&cp(v[i], v[i+1], v[j])<0)
--c;
}
};
if(!cp(n, v[i-1], v[i])&&(cp(n, v[i-2], v[i-1])<0)==(cp(v[i-2], v[i-1], v[i])<0))
s.pop_back();
else if(cp(n, v[i-1], v[i])<=0&&cp(n, v[i-2], v[i-1])>0&&cp(v[i-2], v[i-1], v[i])<0) {
while(cp(n, v[s.back()], v[i])<=0)
++i;
s.pop_back();
ul();
} else if(cp(n, v[i-1], v[i])>0&&(cp(n, v[i-2], v[i-1])>=0||cp(v[i-2], v[i-1], v[i])<0))
ul();
else if(cp(n, v[i-1], v[i])>=0)
while(cp(n, v[s.back()], v[i])>=0)
++i;
s.push_back(i);
}
out(s.size());
putchar_unlocked('\n');
for(int a : s)
b[v[a]]=1;
for(int i=0; i<n; ++i) {
if(b[i]) {
out(i+1);
putchar_unlocked(' ');
}
}
}
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_unlocked('\n');
for(auto e : ans ) out(e+1) , putchar_unlocked(' ') ;
}