Advertisement
Tooster

otoczka-now working

Nov 19th, 2015
288
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.53 KB | None | 0 0
  1. #include <cstdio>
  2. #include <functional>
  3. #include <algorithm>
  4. #include <math.h>
  5. #include <queue>
  6.  
  7. using namespace std;
  8.  
  9. struct point {
  10.     int x;
  11.     int y;
  12. };
  13. point P1;
  14.  
  15. int iloczyn(point a, point b, point c) {
  16.     int pole = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
  17.     if (pole > 0)
  18.         return -1;
  19.     else if (pole < 0)
  20.         return 1;
  21.     return 0;
  22. }
  23.  
  24. int dist(point a, point b) {
  25.     int dx = a.x - b.x, dy = a.y - b.y;
  26.     return dx*dx + dy*dy;
  27. }
  28.  
  29. bool comp(point a, point b){
  30.     int order = iloczyn(a, b, P1);
  31.     if (order == 0)
  32.         return !(dist(P1, a) < dist(P1, b));
  33.     return !(order == -1);
  34. }
  35.  
  36. int main() {
  37.     P1.x = 500000;
  38.     P1.y = 500000;
  39.  
  40.     int n;      scanf("%d", &n);
  41.  
  42.     point *tab = new point[n-1];
  43.  
  44.     int x, y;       scanf("%d %d", &x, &y);      P1.x = x; P1.y = y;
  45.  
  46.     //////////////////////////////////////
  47.     for (int i = 0; i < n-1; i++) {
  48.         scanf("%d %d", &x, &y);
  49.         tab[i].x = x; tab[i].y = y;
  50.         if (tab[i].x < P1.x || (tab[i].x == P1.x && tab[i].y < P1.y)) {
  51.             swap(P1, tab[i]);
  52.         }
  53.     }
  54.     sort(tab, tab + n-1, comp);
  55.  
  56.     vector<point> otoczka;
  57.     otoczka.push_back(tab[0]);
  58.     otoczka.push_back(tab[1]);
  59.     otoczka.push_back(tab[2]);
  60.     for (int i = 3; i < n - 1; i++) {
  61.         point top = otoczka.back();
  62.         otoczka.pop_back();
  63.         while (iloczyn(otoczka.back(), top, tab[i]) == -1) {
  64.             top = otoczka.back();
  65.             otoczka.pop_back();
  66.         }
  67.         otoczka.push_back(top);
  68.         otoczka.push_back(tab[i]);
  69.     }
  70.     //////////////////////////////////////
  71.    
  72.     printf("%c", 'X');
  73.     return 0;
  74. }
  75. //@author Tooster
  76. /*
  77. 5
  78. 1 1
  79. 1 2
  80. 2 3
  81. 3 2
  82. 2 1
  83.  
  84. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement