#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using iter_t = list<int>::iterator;
const int __ = 2e5;
int n;
struct Deg {
ll x, y;
Deg (ll x, ll y): x(x), y(y) { }
friend bool operator==(const Deg lhs, const Deg rhs) { return rhs.x*lhs.y==lhs.x*rhs.y ; }
friend bool operator<(const Deg lhs, const Deg rhs) {
//cout << " Comparing Deg(" << lhs.x << "," << lhs.y << ") < Deg(" << rhs.x << "," << rhs.y << ")\n";
return rhs.x*lhs.y<lhs.x*rhs.y ;
};
friend bool operator<=(const Deg lhs, const Deg rhs) { return rhs.x*lhs.y<=lhs.x*rhs.y ; }
};
struct Point {
ll x, y;
friend bool operator<(const Point lhs, const Point rhs) {
ll d1 = lhs.dist2(), d2 = rhs.dist2();
ll v1 = rhs.x*lhs.y, v2 = lhs.x*rhs.y;
if (v1==v2) return d1<d2;
return v1<v2;
}
ll dist2() const { return x*x+y*y; }
Deg deg() const { return Deg(x,y); }
ll ccw(const Point lhs, const Point rhs) { return (lhs.x-x)*(rhs.y-y)-(lhs.y-y)*(rhs.x-x);}
} p[__];
struct Seg {
vector<int> data;
Seg *prev;
bool inc;
int dup;
/*
void print() {
cout << " Seg " << (inc? "inc":"dec") << ": [";
for (auto v : data) cout << (v+1) << ' ';
cout << "]\n";
}
*/
Seg (bool inc) : prev(nullptr), inc(inc), dup(0) { }
void pop_back() { data.pop_back(); }
bool push_back(int v) {
if (!data.size()) {
//cout << " Empty seg, adding " << (v+1) << '\n';
data.push_back(v);
return true;
}
auto last = data.back();
auto _th = p[v].deg(), th = p[last].deg();
auto _d = p[v].dist2(), d = p[last].dist2();
auto cmp_th = [&]() { return inc? th < _th : _th < th; };
if (dup) {
if (cmp_th()) {
int v0 = data[data.size()-2], v1 = data.back();
data.pop_back(); data.pop_back();
data.push_back(dup==1? v1 : v0);
data.push_back(v);
dup = 0;
return true;
}
if (dup==1) {
int v0 = data.back();
data.pop_back(); data.pop_back();
data.push_back(v0);
return false;
}
return true;
} else if (th == _th) {
dup = d < _d ? 1 : 2;
data.push_back(v);
return true;
}
if (!cmp_th()) {
if (data.size()>1 && (inc? p[data[0]].deg() < _th : _th < p[data[0]].deg()) && d < _d) {
//cout << " Hiding " << (v+1) << " due to angle\n";
return true;
}
//cout << " Failed to add " << (v+1) << " due to angle\n";
return false;
}
//cout << " Adding " << (v+1) << '\n';
data.push_back(v);
//print();
return true;
}
};
struct SegList {
Seg *head;
bool inc;
SegList (bool inc): inc(inc) { head = new Seg(inc); }
int back() { return head->data.back(); }
bool empty() {
return head==nullptr || head->data.size()==0;
}
/*
void print() {
cout << "SegList " << (inc? "inc":"dec") << ":\n";
for (Seg *cur = head; cur!=nullptr; cur=cur->prev) {
cur->print();
}
}
*/
bool operator > ( const Point& pt ) const {
return head->data.size()>0 &&
(inc ? pt < p[head->data.back()] : p[head->data.back()] < pt);
}
void pop_back(bool remove_empty=true) {
head->data.pop_back();
if (!head->data.size() && remove_empty) {
Seg *old = head;
head = head->prev;
delete old;
}
}
bool push_back(int v, bool make_seg=false) {
//cout << " Pushing " << (v+1) << " to seglist " << (inc? "inc":"dec") << '\n';
if (!make_seg) return head->push_back(v);
Seg *x = new Seg(inc);
x->prev = head;
head = x;
return head->push_back(v);
}
vector<int> to_vector() {
vector<int> res;
for (Seg *cur = head; cur!=nullptr; cur=cur->prev) {
for (int i=0; i<(int)cur->data.size(); ++i) {
res.push_back(cur->data[i]);
}
}
return res;
}
};
struct Circuit {
SegList seg[2] = {SegList(true), SegList(false)};
int i;
Circuit() : i(0) { }
void add(int v) {
if (seg[0].empty() && seg[1].empty()) {
seg[i].push_back(v);
//cout << " Initial add\n";
return;
}
if (!seg[i].push_back(v)) {
//cout << " Failed to add to seg " << (i? "inc":"dec") << '\n';
if (!seg[!i].empty()) {
//cout << " Adjusting other seg " << (i? "dec":"inc") << '\n';
int l = seg[!i].back(); seg[!i].pop_back(false);
///cout << " Popped back : " << (l+1) << '\n';
//seg[!i].print();
while(seg[!i] > p[seg[i].back()]) {
seg[!i].pop_back();
//cout << " Popped back to adjust\n";
//seg[!i].print();
}
seg[!i].push_back(l);
if (!(seg[!i] > p[v]))
{
//cout << " Removing last from other seg\n";
seg[!i].pop_back();
//seg[!i].print();
}
}
//cout << " Switching seg\n";
seg[!i].push_back(v, true);
i = !i;
//seg[0].print();
//seg[1].print();
}
}
vector<int> to_vector() {
vector<int> res;
for (int k=0; k<2; ++k) {
auto vk = seg[k].to_vector();
res.insert(res.end(), vk.begin(), vk.end());
}
return res;
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
int max_i, min_i;
Point max_pt = {1, 0}, min_pt = {0, 1};
for (int i=0; i<n; ++i) {
cin >> p[i].x >> p[i].y;
if (max_pt<p[i]) { max_pt = p[i]; max_i = i; }
if (p[i]<min_pt) { min_pt = p[i]; min_i = i; }
}
Circuit circ = Circuit();
int di = min_pt.ccw(p[(min_i+1)%n],p[(min_i-1+n)%n])>0? -1 : 1;
auto next = [&](int i) { return (i+di+n)%n; };
for (int i=min_i,_break=0; !_break; i=next(i)) {
if (!_break&&i==max_i) ++_break;
//cout << "Adding point " << i << " (" << p[i].x << "," << p[i].y << ")\n";
circ.add(i);
}
auto vi = circ.to_vector();
sort(vi.begin(), vi.end());
cout << vi.size() << '\n';
for (auto v : vi) cout << (v+1) << ' ';
cout << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |