#include <bits/stdc++.h>
static struct FASTIO {
char READ_CHARACTER; bool REMAINING_CHARACTER = false;
inline void ignore(); inline void flush();
template <typename T> inline bool READ_INT(T &x); template <typename T> inline bool READ_STRING(T &x);
/* Fast I/O Code Optimizer */
template<size_t N> inline bool READ_CHAR_ARRAY(char (&x)[N]); template<size_t N> inline bool READ_VAR(char (&x)[N]);
/* A tool to optimize execution time of C++ codes by replacing methods of reading and writing variables */
template <typename T> inline bool READ_CHAR(T &x); inline bool READ_CHAR_ARRAY(char*& x); inline bool READ_GETLINE(std::string &x);
/* Use it on fastio.pythonanywhere.com */
template <typename T> inline bool READ_FLOAT(T &x); template <typename T> inline bool READ_DOUBLE(T &x);
/* Github Project: github.com/bfs07/Fast-IO-Code-Optimizer */
template<std::size_t N> inline bool READ_BITSET(std::bitset<N> &bit); template<std::size_t N> inline bool READ_VAR(std::bitset<N> &bit);
inline bool READ_VAR(bool &x); inline bool READ_VAR(short int &x); inline bool READ_VAR(int &x);
inline bool READ_VAR(long int &x); inline bool READ_VAR(long long int &x); inline bool READ_VAR(unsigned short int &x);
inline bool READ_VAR(unsigned int &x); inline bool READ_VAR(unsigned long &x); inline bool READ_VAR(unsigned long long &x);
inline bool READ_VAR(std::string &x); inline bool READ_VAR(char &x); inline bool READ_VAR(char*& x); inline bool READ_VAR(float &x);
inline bool READ_VAR(double &x); inline bool READ_VAR(long double &x); template <typename T> inline void WRITE_INT(T x);
inline void WRITE_STRING(std::string &x); inline void WRITE_CHAR(char x); inline void WRITE_CHAR_ARRAY(const char *x);
inline void WRITE_FLOAT(float x); template <typename T> inline void WRITE_DOUBLE(T x); inline void WRITE_VAR(bool x);
inline void WRITE_VAR(short int x); inline void WRITE_VAR(int x); inline void WRITE_VAR(long int x); inline void WRITE_VAR(long long int x);
inline void WRITE_VAR(unsigned short int x); inline void WRITE_VAR(unsigned int x); inline void WRITE_VAR(unsigned long x);
inline void WRITE_VAR(unsigned long long x); inline void WRITE_VAR(char x); inline void WRITE_VAR(const char *x);
inline void WRITE_VAR(std::string &x); inline void WRITE_VAR(float x); inline void WRITE_VAR(double x); inline void WRITE_VAR(long double x);
template<std::size_t N> inline void WRITE_VAR(std::bitset<N> &bit); template<std::size_t N> inline void WRITE_BITSET(std::bitset<N> &bit);
} __FIO__;
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#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] ;
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 ; i > 0 ; i-- )
{
l[i] = min(l[i<<1], l[i<<1|1] ) ;
r[i] = max(r[i<<1], r[i<<1|1] ) ;
}
}
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 ) ) ;
}
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++ ;
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 ) ;
}
vector<int> ans ;
for(int i=0 ; i < N ; i++ )
{
if(i && sorted[i-1].first%sorted[i].first == 0 ) continue ;
if(seg.qry(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") ;
}
#undef sz
#undef lp
#undef all
#undef sz
#undef debug
#undef lp
#undef pb
#undef ff
#undef ss
#undef mk
#undef pii
#undef ll
#undef all
inline void FASTIO::ignore() {
if(REMAINING_CHARACTER == true) REMAINING_CHARACTER = false; else READ_CHARACTER = getchar();
}
inline void FASTIO::flush() {
fflush(stdout);
}
// cin modifications
template <typename T>
inline bool FASTIO::READ_INT(T &x) {
x = 0; T sig = 1;
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
while (!isdigit(READ_CHARACTER) && READ_CHARACTER != EOF) sig = (READ_CHARACTER == '-' ? -sig : sig), READ_CHARACTER = getchar();
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
while (isdigit(READ_CHARACTER)) x = x * 10 + READ_CHARACTER - '0', READ_CHARACTER = getchar();
x *= sig; REMAINING_CHARACTER = true;
return true;
}
template <typename T>
inline bool FASTIO::READ_STRING(T &x) {
x = "";
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
REMAINING_CHARACTER = true;
return true;
}
inline bool FASTIO::READ_GETLINE(std::string &x) {
x = "";
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
while ((READ_CHARACTER != '\n' && READ_CHARACTER != EOF)) x += READ_CHARACTER, READ_CHARACTER = getchar();
REMAINING_CHARACTER = false;
return true;
}
template <typename T>
inline bool FASTIO::READ_CHAR(T &x) {
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
x = READ_CHARACTER; REMAINING_CHARACTER = false;
return true;
}
template<size_t N>
inline bool FASTIO::READ_CHAR_ARRAY(char (&x)[N]) {
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
char *ptr = &x[0];
while ((READ_CHARACTER != '\n' && READ_CHARACTER != '\t' && READ_CHARACTER != ' ' && READ_CHARACTER != EOF)) *ptr++ = READ_CHARACTER, READ_CHARACTER = getchar();
*ptr = '\0', REMAINING_CHARACTER = true;
return true;
}
inline bool FASTIO::READ_CHAR_ARRAY(char*& x) {
std::string y;
if(READ_STRING(y) == false)
return false;
x = new char[(int)y.size() + 1];
strcpy(x, y.c_str());
return true;
}
template <typename T>
inline bool FASTIO::READ_FLOAT(T &x) {
return (scanf("%f", &x) != EOF);
}
template <typename T>
inline bool FASTIO::READ_DOUBLE(T &x) {
double y;
if(scanf("%lf", &y) == EOF) return false;
x = y;
return true;
}
template<std::size_t N>
inline bool FASTIO::READ_BITSET(std::bitset<N> &x) {
if(!REMAINING_CHARACTER) READ_CHARACTER = getchar(), REMAINING_CHARACTER = true; else REMAINING_CHARACTER = false;
while ((READ_CHARACTER == '\n' || READ_CHARACTER == '\t' || READ_CHARACTER == ' ')) READ_CHARACTER = getchar();
if(READ_CHARACTER == EOF) return REMAINING_CHARACTER = false, false;
int i = 0; REMAINING_CHARACTER = true;
while (READ_CHARACTER == '0' || READ_CHARACTER == '1') x[i++] = READ_CHARACTER - '0', READ_CHARACTER = getchar();
return true;
}
inline bool FASTIO::READ_VAR(short int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(long int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(long long int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(unsigned short int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(unsigned int &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(unsigned long &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(unsigned long long &x) {
return READ_INT(x);
}
inline bool FASTIO::READ_VAR(std::string &x) {
return READ_STRING(x);
}
inline bool FASTIO::READ_VAR(char &x) {
return READ_CHAR(x);
}
template<size_t N>
inline bool FASTIO::READ_VAR(char (&x)[N]) {
return READ_CHAR_ARRAY(x);
}
inline bool FASTIO::READ_VAR(char*& x) {
return READ_CHAR_ARRAY(x);
}
inline bool FASTIO::READ_VAR(float &x) {
return READ_FLOAT(x);
}
inline bool FASTIO::READ_VAR(double &x) {
return READ_DOUBLE(x);
}
inline bool FASTIO::READ_VAR(long double &x) {
return READ_DOUBLE(x);
}
template<std::size_t N>
inline bool FASTIO::READ_VAR(std::bitset<N> &x) {
return READ_BITSET(x);
}
// cout modifications
template <typename T>
inline void FASTIO::WRITE_INT(T x) {
if (x < 0) {putchar('-'); x = -x; }
char writeBuffer[20], *writePtr = writeBuffer;
do {
*writePtr++ = '0' + x % 10;
x /= 10;
}
while (x);
do { putchar(*--writePtr); }
while (writePtr > writeBuffer);
}
inline void FASTIO::WRITE_CHAR(char x) {
putchar(x);
}
inline void FASTIO::WRITE_CHAR_ARRAY(const char *x) {
while(*x != '\0')
putchar(*x++);
}
inline void FASTIO::WRITE_STRING(std::string &x) {
for(char c: x)
putchar(c);
}
inline void FASTIO::WRITE_FLOAT(float x) {
printf("%f", x);
}
template <typename T>
inline void FASTIO::WRITE_DOUBLE(T x) {
printf("%lf", (double)x);
}
template<std::size_t N>
inline void FASTIO::WRITE_BITSET(std::bitset<N> &x) {
for(int i = (int)x.size() - 1; i >= 0; i--)
putchar(x[i] + 48);
}
inline void FASTIO::WRITE_VAR(bool x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(short int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(long int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(long long int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(unsigned short int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(unsigned int x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(unsigned long x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(unsigned long long x) {
WRITE_INT(x);
}
inline void FASTIO::WRITE_VAR(std::string &x) {
WRITE_STRING(x);
}
inline void FASTIO::WRITE_VAR(char x) {
WRITE_CHAR(x);
}
inline void FASTIO::WRITE_VAR(const char *x) {
WRITE_CHAR_ARRAY(x);
}
inline void FASTIO::WRITE_VAR(float x) {
WRITE_FLOAT(x);
}
inline void FASTIO::WRITE_VAR(double x) {
WRITE_DOUBLE(x);
}
inline void FASTIO::WRITE_VAR(long double x) {
WRITE_DOUBLE(x);
}
template<std::size_t N>
inline void FASTIO::WRITE_VAR(std::bitset<N> &x) {
WRITE_BITSET(x);
}
Compilation message
circuit.cpp: In instantiation of 'void FASTIO::WRITE_INT(T) [with T = bool]':
circuit.cpp:466:14: required from here
circuit.cpp:425:9: warning: comparison of constant '0' with boolean expression is always false [-Wbool-compare]
425 | if (x < 0) {putchar('-'); x = -x; }
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
15980 KB |
Output is correct |
| 2 |
Correct |
11 ms |
16108 KB |
Output is correct |
| 3 |
Correct |
12 ms |
16364 KB |
Output is correct |
| 4 |
Correct |
13 ms |
16364 KB |
Output is correct |
| 5 |
Correct |
18 ms |
16872 KB |
Output is correct |
| 6 |
Correct |
16 ms |
16872 KB |
Output is correct |
| 7 |
Correct |
23 ms |
17636 KB |
Output is correct |
| 8 |
Correct |
15 ms |
16688 KB |
Output is correct |
| 9 |
Correct |
15 ms |
16744 KB |
Output is correct |
| 10 |
Correct |
16 ms |
16872 KB |
Output is correct |
| 11 |
Correct |
17 ms |
17000 KB |
Output is correct |
| 12 |
Correct |
19 ms |
17636 KB |
Output is correct |
| 13 |
Correct |
31 ms |
18436 KB |
Output is correct |
| 14 |
Correct |
29 ms |
19040 KB |
Output is correct |
| 15 |
Correct |
32 ms |
19808 KB |
Output is correct |
| 16 |
Correct |
56 ms |
23516 KB |
Output is correct |
| 17 |
Correct |
86 ms |
23516 KB |
Output is correct |
| 18 |
Execution timed out |
105 ms |
30928 KB |
Time limit exceeded |
| 19 |
Execution timed out |
105 ms |
31016 KB |
Time limit exceeded |
| 20 |
Execution timed out |
183 ms |
30928 KB |
Time limit exceeded |
