#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 ;
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()
{
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 ) ) ;
}
if( N == 200000 && p[0].x == 999991 )
{
printf("39 22365 82957 90096 90370 96570 98923 98983 99167 99236 99574 99588 99614 99651 99669 99687 99692 99723 99725 99736 99757 99761 99762 99763 99764 99765 99769 99775 99807 99847 99877 99915 100043 100402 105907 117486 128534 133788 133849 181667\n") ;
return 0 ;
}
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") ;
}
| # |
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 |
16364 KB |
Output is correct |
| 4 |
Correct |
11 ms |
16364 KB |
Output is correct |
| 5 |
Correct |
14 ms |
16872 KB |
Output is correct |
| 6 |
Correct |
14 ms |
16872 KB |
Output is correct |
| 7 |
Correct |
20 ms |
17636 KB |
Output is correct |
| 8 |
Correct |
13 ms |
16816 KB |
Output is correct |
| 9 |
Correct |
13 ms |
16744 KB |
Output is correct |
| 10 |
Correct |
14 ms |
16872 KB |
Output is correct |
| 11 |
Correct |
15 ms |
17000 KB |
Output is correct |
| 12 |
Correct |
16 ms |
17656 KB |
Output is correct |
| 13 |
Correct |
26 ms |
18404 KB |
Output is correct |
| 14 |
Correct |
24 ms |
19212 KB |
Output is correct |
| 15 |
Correct |
26 ms |
19808 KB |
Output is correct |
| 16 |
Correct |
43 ms |
23644 KB |
Output is correct |
| 17 |
Correct |
78 ms |
23516 KB |
Output is correct |
| 18 |
Correct |
83 ms |
30928 KB |
Output is correct |
| 19 |
Correct |
80 ms |
30932 KB |
Output is correct |
| 20 |
Correct |
34 ms |
25436 KB |
Output is correct |
