#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
typedef long double lf;
typedef long long ll;
typedef pair<int, int> point;
const int MAXN = 1e5 + 5, inf = 1e9;
const lf eps = 1e-9;
int x[MAXN], y[MAXN];
lf K;
lf kk(int X, int Y) {
return (lf) Y / X;
}
struct duz {
lf k, l;
lf lo, hi;
bool usp;
duz() {}
duz(int i, int j) {
lo = kk(x[i], y[i]);
hi = kk(x[j], y[j]);
if(lo > hi) swap(lo, hi);
if(x[i] == x[j]) {
usp = true;
k = x[i];
}
else {
k = (lf) (y[i] - y[j]) / (x[i] - x[j]);
l = (lf) y[i] - k * x[i];
usp = false;
}
}
friend bool operator < (const duz &A, const duz &B);
} line[MAXN];
lf calc(duz A) {
if(A.usp) return A.k;
return A.l / (K - A.k);
}
bool operator < (const duz &A, const duz &B) {
lf x1 = calc(A), x2 = calc(B);
//
// if(x1 == x2 && A.lo == K && B.lo == K) {
// K += eps;
// x1 = calc(A);
// x2 = calc(B);
// K -= eps;
// }
// else {
// K -= eps;
// x1 = calc(A);
// x2 = calc(B);
// K += eps;
// }
return x1 < x2;
}
vector<pair<lf, point> > e;
void add(int i, int j) {
line[i] = duz(i, j);
lf k1 = kk(x[i], y[i]);
lf k2 = kk(x[j], y[j]);
if(k1 > k2) swap(k1, k2);
e.push_back({k1 + eps, {0, i}});
e.push_back({k2 - eps, {2, i}});
}
multiset<duz> s;
unordered_map<lf, int> m;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n; cin >> n;
REP(i, n) {
cin >> x[i] >> y[i];
e.push_back({kk(x[i], y[i]), {1, i}});
m[kk(x[i], y[i])] = max(m[kk(x[i], y[i])], inf - x[i]);
}
REP(i, n) {
int j = (i + 1) % n;
add(i, j);
}
sort(e.begin(), e.end());
vector<int> sol(n, 0);
for(auto p: e) {
K = p.first;
if(p.second.first == 0) {
s.insert(line[p.second.second]);
}
if(p.second.first == 1) {
if(sz(s) == 0) continue;
duz X = *s.begin();
if(calc(X) < x[p.second.second]) {
sol[p.second.second] = true;
}
}
if(p.second.first == 2) {
if(s.find(line[p.second.second]) == s.end() continue;
s.erase(s.lower_bound(line[p.second.second]));
}
}
vector<int> ans;
REP(i, n) {
if(!sol[i] && m[kk(x[i], y[i])] == inf - x[i]) ans.push_back(i);
}
cout << sz(ans) << endl;
for(auto xx: ans) {
cout << xx + 1 << " ";
}
}
Compilation message
circuit.cpp: In function 'int main()':
circuit.cpp:123:10: warning: init-statement in selection statements only available with -std=c++1z or -std=gnu++1z
if(s.find(line[p.second.second]) == s.end() continue;
^
circuit.cpp:123:51: error: expected ';' before 'continue'
if(s.find(line[p.second.second]) == s.end() continue;
^~~~~~~~
circuit.cpp:124:52: error: expected ')' before ';' token
s.erase(s.lower_bound(line[p.second.second]));
^
circuit.cpp:124:14: error: could not convert 's.std::multiset<duz>::erase(s.std::multiset<duz>::lower_bound(line[p.std::pair<long double, std::pair<int, int> >::second.std::pair<int, int>::second]))' from 'std::multiset<duz>::iterator {aka std::_Rb_tree_const_iterator<duz>}' to 'bool'
s.erase(s.lower_bound(line[p.second.second]));
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
