#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 N ;
int myId[MAX] ;
ll 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 print() { printf("%lld %lld\n" , x , y) ; }
void read() { scanf("%lld %lld", &x, &y) ; }
} ;
struct Line
{
Point p1, p2 ;
Line( Point p1 = Point(0,0) , Point p2 = Point(0,0) ) : p1(p1) , p2(p2) {}
void print()
{
printf("(%lld, %lld) and (%lld, %lld)\n", p1.x, p1.y, p2.x, p2.y ) ;
}
} ;
bool isLess(ll num1, ll den1, ll num2, ll den2 )
{
//It doesn't happen that den < 0, because x is always positive
ll q1 = num1/den1 ;
ll q2 = num2/den2 ;
ll r1 = num1%den1 ;
ll r2 = num2%den2 ;
if( q1 != q2 ) return q1 < q2 ;
if( r1 == 0 || r2 == 0 ) return r1 == 0 && r2 > 0 ;
return isLess(den2, r2, den1, r1 ) ;
}
ll getNum( Line t, int id )
{
return den[id] * ( t.p1.y*t.p2.x - t.p1.x*t.p2.y ) ;
}
ll getDen(Line t, int id )
{
return den[id] * ( t.p1.y - t.p2.y ) - num[id] * (t.p1.x-t.p2.x ) ;
}
struct Seg
{
Line tree[MAX*4] ;
int m(int l, int r ) { return (l+r)>>1 ; }
void addLine(int pos, int l, int r, int beg, int en, Line t )
{
if( l > en || r < beg ) return ;
if( l >= beg && r <= en )
{
if( tree[pos].p1 == Point(0,0) ) return (void)(tree[pos] = t ) ;
//check if tree[pos] is less than t
vector<bool> ok ;
for(auto e : {l , r } )
{
ll num1 = getNum(tree[pos], e) ;
ll den1 = getDen(tree[pos], e ) ;
ll num2 = getNum(t, e ) ;
ll den2 = getDen(t, e ) ;
if(den1 < 0 ) num1 = -num1 , den1 = -den1 ;
if( den2 < 0 ) num2 = -num2, den2 = -den2 ;
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 ;
ok.push_back( isLess(num1, den1, num2, den2 ) ) ;
}
if( !ok[0] && !ok[1] ) tree[pos] = t ;
return ;
}
addLine(pos<<1 , l , m(l,r) , beg, en, t ) ;
addLine(pos<<1|1, m(l,r)+1, r, beg, en, t ) ;
}
bool qry(int pos, int l, int r, int x, Point p )
{
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( tree[pos].p1 != p && tree[pos].p2 != p && tree[pos].p1 != Point(0,0) && (val1 < 0 ) != (val2 < 0) )
return false ;
if( l == r ) return true ;
if( x <= m(l,r) ) return qry(pos<<1 , l , m(l,r), x, p ) ;
return qry(pos<<1|1, m(l,r)+1, r, x, p ) ;
}
void print(int pos, int l, int r )
{
printf("Covering [%d,%d], there is " , l ,r ) ; tree[pos].print() ;
if( l == r ) return ;
print(pos<<1 , l , m(l,r) ) ;
print(pos<<1|1, m(l,r)+1, r ) ;
}
} seg ;
int main()
{
scanf("%d", &N ) ;
vector<Point> p(N) ;
vector< pair<Point, int> > sorted ;
for(int i = 0 ; i < N ; i++ )
{
p[i].read() ;
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 ;
} ) ;
for(int i = 0 , j = -1 ; 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 ;
}
//for(int i= 0 ; i < N ; i++ ) printf("%lld %lld\n", den[i], num[i] ) ;
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 ) swap(l,r) ;
if(l != r )
seg.addLine(1, 0 , N-1, l,r, Line( p[i], p[nxt] ) ) ;
}
//seg.print(1,0,N-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(1,0,N-1, 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") ;
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
148 | scanf("%d", &N ) ;
| ~~~~~^~~~~~~~~~~
circuit.cpp: In member function 'void Point::read()':
circuit.cpp:35:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
35 | void read() { scanf("%lld %lld", &x, &y) ; }
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
25452 KB |
Output is correct |
| 2 |
Correct |
15 ms |
25452 KB |
Output is correct |
| 3 |
Correct |
16 ms |
25708 KB |
Output is correct |
| 4 |
Correct |
18 ms |
25836 KB |
Output is correct |
| 5 |
Correct |
30 ms |
26216 KB |
Output is correct |
| 6 |
Correct |
31 ms |
26216 KB |
Output is correct |
| 7 |
Correct |
48 ms |
26980 KB |
Output is correct |
| 8 |
Correct |
26 ms |
26032 KB |
Output is correct |
| 9 |
Correct |
28 ms |
26088 KB |
Output is correct |
| 10 |
Correct |
30 ms |
26216 KB |
Output is correct |
| 11 |
Correct |
33 ms |
26344 KB |
Output is correct |
| 12 |
Correct |
30 ms |
26856 KB |
Output is correct |
| 13 |
Correct |
69 ms |
27748 KB |
Output is correct |
| 14 |
Correct |
50 ms |
28256 KB |
Output is correct |
| 15 |
Correct |
59 ms |
29024 KB |
Output is correct |
| 16 |
Execution timed out |
104 ms |
32604 KB |
Time limit exceeded |
| 17 |
Execution timed out |
229 ms |
32732 KB |
Time limit exceeded |
| 18 |
Execution timed out |
203 ms |
39716 KB |
Time limit exceeded |
| 19 |
Execution timed out |
193 ms |
39760 KB |
Time limit exceeded |
| 20 |
Execution timed out |
503 ms |
40016 KB |
Time limit exceeded |
