Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstdlib>
- #include <cstring>
- #include <cmath>
- #include <cassert>
- #include <algorithm>
- #include <string>
- #include <vector>
- #include <deque>
- #include <queue>
- #include <map>
- #include <set>
- using namespace std;
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #define pb push_back
- #define mp make_pair
- #define sz(x) ((int)(x).size())
- typedef long long ll;
- typedef vector<ll> vll;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- typedef vector<bool> vb;
- typedef vector<vb> vvb;
- typedef pair<int, int> pii;
- int sgn(ll x) { return x < 0 ? -1 : !!x; }
- struct pt {
- int x, y, id, id0;
- pt() : x(0), y(0) {}
- pt(int _x, int _y) : x(_x), y(_y) {}
- pt operator-(const pt &p2) const { return pt(x - p2.x, y - p2.y); }
- ll operator*(const pt &p2) const { return ll(x) * p2.y - ll(y) * p2.x; }
- ll dist2() const { return ll(x) * x + ll(y) * y; }
- };
- bool rcmp(const pt &a, const pt &b) { if (a * b) return a * b > 0; return a.dist2() < b.dist2(); }
- bool icmp(const pt &a, const pt &b) { return a.id < b.id; }
- bool cross(pt a1, pt b1, pt a2, pt b2) {
- if ( sgn((a2 - a1) * (b1 - a1)) * sgn((b2 - a1) * (b1 - a1)) > 0) return false;
- swap(a1, a2);
- swap(b1, b2);
- if ( sgn((a2 - a1) * (b1 - a1)) * sgn((b2 - a1) * (b1 - a1)) > 0) return false;
- return true;
- }
- bool is_in(int l, int r, int x) {
- if (l > r) swap(l, r);
- return l <= x && x <= r;
- }
- bool contains(pt a, pt b, pt p) {
- if ((b - a) * (p - a)) return false;
- return is_in(a.x, b.x, p.x) && is_in(a.y, b.y, p.y);
- }
- int main() {
- #ifdef DEBUG
- freopen("std.in", "r", stdin);
- freopen("std.out", "w", stdout);
- #endif
- int n;
- while (scanf("%d", &n) >= 1) {
- vector<pt> pts(n);
- for (int i = 0; i < n; i++)
- scanf("%d%d", &pts[i].x, &pts[i].y), pts[i].id = i + 1;
- if (n <= 1000) {
- vi res;
- for (int i = 0; i < n; i++) {
- bool g = true;
- pt p = pts[i];
- for (int i2 = 0; i2 < n; i2++) {
- if (i2 != i)
- if (contains(pt(), p, pts[i2])) g = false;
- int i3 = i2 + 1; if (i3 == n) i3 = 0;
- if (i2 == i || i3 == i) continue;
- pt a = pts[i2], b = pts[i3];
- if (cross(a, b, pt(), p)) g = false;
- }
- if (g) res.pb(i);
- }
- printf("%d\n", sz(res));
- for (int i = 0; i < sz(res); i++) {
- if (i) printf(" ");
- printf("%d", res[i] + 1);
- }
- printf("\n");
- continue;
- }
- {
- ll sq = 0;
- for (int i = 0; i < n; i++) {
- int ne = i + 1; if (ne >= n) ne = 0;
- sq += pts[i] * pts[ne];
- }
- if (sq > 0)
- reverse(pts.begin(), pts.end());
- }
- rotate(pts.begin(), min_element(pts.begin(), pts.end(), rcmp), pts.end());
- for (int i = 0; i < sz(pts); i++)
- pts[i].id0 = i;
- vector<pt> res;
- res.pb(pts[0]);
- bool mode = true;
- for (int i = 1; i < sz(pts); i++) {
- bool g = true;
- int delMode = -1;
- while (!res.empty()) {
- pt pr = res.back(), cur = pts[i];
- if (pr * cur > 0) {
- break;
- }
- if (!mode) {
- g = false;
- break;
- }
- if (pr * cur == 0) {
- if (cur.dist2() < pr.dist2()) {
- res.pop_back();
- assert(res.empty() || res.back() * cur > 0);
- continue;
- } else {
- g = false;
- break;
- }
- }
- if (delMode < 0) {
- assert(pr.id0 >= 1);
- // pt pr2 = res[sz(res) - 2];
- pt pr2 = pts[pr.id0 - 1];
- // eprintf("%d %d %d\n", pr2.id, pr.id, cur.id);
- delMode = (pr * pr2 < 0);
- delMode = delMode && ((pr2 - pr) * (cur - pr) > 0);
- delMode = !delMode;
- // delMode = ((pr - pr2) * (cur - pr2)) > 0;
- // delMode = delMode && (pr * pr2 < 0);
- // eprintf("delMode=%d\n", delMode);
- if (!delMode) { g = false; break; }
- }
- res.pop_back();
- }
- if (g)
- res.pb(pts[i]);
- mode = g;
- }
- sort(res.begin(), res.end(), icmp);
- printf("%d\n", sz(res));
- for (int i = 0; i < sz(res); i++) {
- if (i) printf(" ");
- printf("%d", res[i].id);
- }
- printf("\n");
- // break;
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment