Advertisement
Guest User

Untitled

a guest
Jan 21st, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.40 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef long double ld;
  5. struct pt {
  6. ll x, y;
  7. };
  8.  
  9. bool cmp (pt a, pt b) {
  10. return a.x < b.x || a.x == b.x && a.y < b.y;
  11. }
  12.  
  13. bool cw (pt a, pt b, pt c) {
  14. return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
  15. }
  16.  
  17. bool ccw (pt a, pt b, pt c) {
  18. return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
  19. }
  20.  
  21. void convex_hull (vector<pt> & a) {
  22. if (a.size() == 1) return;
  23. sort (a.begin(), a.end(), &cmp);
  24. pt p1 = a[0], p2 = a.back();
  25. vector<pt> up, down;
  26. up.push_back (p1);
  27. down.push_back (p1);
  28. for (size_t i=1; i<a.size(); ++i) {
  29. if (i==a.size()-1 || cw (p1, a[i], p2)) {
  30. while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
  31. up.pop_back();
  32. up.push_back (a[i]);
  33. }
  34. if (i==a.size()-1 || ccw (p1, a[i], p2)) {
  35. while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
  36. down.pop_back();
  37. down.push_back (a[i]);
  38. }
  39. }
  40. a.clear();
  41. for (size_t i=0; i<up.size(); ++i)
  42. a.push_back (up[i]);
  43. for (size_t i=down.size()-2; i>0; --i)
  44. a.push_back (down[i]);
  45. }
  46. ll area(pt a, pt b, pt c) {
  47. return abs(a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y));
  48. }
  49. bool inside(pt a, pt b, pt c, pt d) {
  50. return area(a, b, c) == area(a, b, d) + area(a, c, d) + area(b, c, d);
  51. }
  52. bool inside_poly(pt x, vector < pt >& all) {
  53. if (all.size() <= 2) return false;
  54. for (int j = 1; j + 1 < all.size(); j++) {
  55. if (inside(all[0], all[j], all[j + 1], x)) return true;
  56. }
  57. return false;
  58. }
  59. int n;
  60. const int maxN = 1005;
  61. pt t[maxN];
  62. int main () {
  63. ios_base::sync_with_stdio(false);
  64. cin.tie(nullptr);
  65. //freopen("input.txt", "r", stdin);
  66. cin >> n;
  67. bool ok = true;
  68. vector < pt > ch;
  69. for (int i = 1; i <= n; i++) {
  70. cin >> t[i].x >> t[i].y;
  71. if (inside_poly(t[i], ch)) {
  72. ok = false;
  73. break;
  74. }
  75. ch.push_back(t[i]);
  76. convex_hull(ch);
  77. }
  78. ch.clear();
  79. for (int i = n; i >= 1; i--) {
  80. if (inside_poly(t[i], ch)) {
  81. ok = false;
  82. break;
  83. }
  84. ch.push_back(t[i]);
  85. convex_hull(ch);
  86. }
  87. if (ok) cout << "Possible";
  88. else cout << "Impossible";
  89. return 0;
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement