Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef long double ld;
- struct pt {
- ll x, y;
- };
- bool cmp (pt a, pt b) {
- return a.x < b.x || a.x == b.x && a.y < b.y;
- }
- bool cw (pt a, pt b, pt c) {
- return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
- }
- bool ccw (pt a, pt b, pt c) {
- return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
- }
- void convex_hull (vector<pt> & a) {
- if (a.size() == 1) return;
- sort (a.begin(), a.end(), &cmp);
- pt p1 = a[0], p2 = a.back();
- vector<pt> up, down;
- up.push_back (p1);
- down.push_back (p1);
- for (size_t i=1; i<a.size(); ++i) {
- if (i==a.size()-1 || cw (p1, a[i], p2)) {
- while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
- up.pop_back();
- up.push_back (a[i]);
- }
- if (i==a.size()-1 || ccw (p1, a[i], p2)) {
- while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
- down.pop_back();
- down.push_back (a[i]);
- }
- }
- a.clear();
- for (size_t i=0; i<up.size(); ++i)
- a.push_back (up[i]);
- for (size_t i=down.size()-2; i>0; --i)
- a.push_back (down[i]);
- }
- ll area(pt a, pt b, pt c) {
- return abs(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
- }
- bool inside(pt a, pt b, pt c, pt d) {
- return area(a, b, c) == area(a, b, d) + area(a, c, d) + area(b, c, d);
- }
- bool inside_poly(pt x, vector < pt >& all) {
- if (all.size() <= 2) return false;
- for (int j = 1; j + 1 < all.size(); j++) {
- if (inside(all[0], all[j], all[j + 1], x)) return true;
- }
- return false;
- }
- int n;
- const int maxN = 1005;
- pt t[maxN];
- int main () {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- //freopen("input.txt", "r", stdin);
- cin >> n;
- bool ok = true;
- vector < pt > ch;
- for (int i = 1; i <= n; i++) {
- cin >> t[i].x >> t[i].y;
- if (inside_poly(t[i], ch)) {
- ok = false;
- break;
- }
- ch.push_back(t[i]);
- convex_hull(ch);
- }
- ch.clear();
- for (int i = n; i >= 1; i--) {
- if (inside_poly(t[i], ch)) {
- ok = false;
- break;
- }
- ch.push_back(t[i]);
- convex_hull(ch);
- }
- if (ok) cout << "Possible";
- else cout << "Impossible";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement