andmej / acm

My solutions for problems from the UVa Online Judge (Valladolid).

acm / 10005 - Packing polygons / 10005.2.cpp
100644 116 lines (94 sloc) 2.623 kb
raw blame history 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

/*
  Accepted. Graham Scan.
 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include <math.h>
#include <stdio.h>
 
using namespace std;
 
 
//const double pi = 2*acos(0);
const double pi = 3.14159265;
 
struct point{
  int x,y;
  point() {}
  point(int X, int Y) : x(X), y(Y) {}
};
 
point pivot;
 
ostream& operator<< (ostream& out, const point& c)
{
  out << "(" << c.x << "," << c.y << ")";
  return out;
}
 
inline double dist(const point &a, const point &b){
  return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
 
inline int distsqr(const point &a, const point &b){
  return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
 
//retorna si c esta a la izquierda de el segmento AB
inline int cross(const point &a, const point &b, const point &c){
  return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}
 
//Self < that si esta a la derecha del segmento Pivot-That
bool angleCmp(const point &self, const point &that){
  int t = cross(pivot, that, self);
  if (t < 0) return true;
  if (t == 0){
    //Self < that si está más cerquita
    return (distsqr(pivot, self) < distsqr(pivot, that));
  }
  return false;
}
 
 
//vector p tiene los puntos ordenados anticlockwise
vector<point> graham(vector<point> p){
  //Metemos el más abajo más a la izquierda en la posición 0
  for (int i=1; i<p.size(); ++i){
    if (p[i].y < p[0].y || (p[i].y == p[0].y && p[i].x < p[0].x ))
      swap(p[0], p[i]);
  }
  
  pivot = p[0];
  sort(p.begin(), p.end(), angleCmp);
 
  //Ordenar por ángulo y eliminar repetidos.
  //Si varios puntos tienen el mismo angulo el más lejano queda después en la lista
  vector<point> chull(p.begin(), p.begin()+3);
 
  //Ahora sí!!!
  for (int i=3; i<p.size(); ++i){
    while ( chull.size() >= 2 && cross(chull[chull.size()-2], chull[chull.size()-1], p[i]) <= 0){
      chull.erase(chull.end() - 1);
    }
    chull.push_back(p[i]);
  }
 
  return chull;
}
 
int main(){
  int cases;
  cin >> cases;
  bool first = true;
  while (cases--){
    if (!first) cout << endl;
    first = false;
    int n, l;
    cin >> n >> l;
    vector<point> p;
    for (int i=0; i<n; ++i){
      int x, y;
      cin >> x >> y;
      p.push_back(point(x,y));      
    }
    
    vector<point> chull = graham(p);
     
    /*cout << "chull es:  " << endl;
      for (int i=0; i<chull.size(); ++i){
      cout << chull[i] << " ";
      }
      cout <<  endl;*/
 
    double perimeter = 0.0;
    for (int i=0; i<chull.size(); ++i){
      int j = (i+1)%chull.size();
      perimeter += dist(chull[i], chull[j]);
    }
 
    printf("%.0f\n", perimeter + 2*pi*l);
  }
  return 0;
}