v 0. Pasted by slipstak2 as cpp at 2011-01-17 21:14:49 MSK and set expiration to never.

Paste will expire never.

  1. // Меньшиков. Тренировка 15.
  2. // 15D. Стена [wall]
  3. // ibelyaev: 16Jan2011
  4.  
  5. #include <iostream>
  6. #include <cstdio>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <cmath>
  10. using namespace std;
  11.  
  12. typedef pair<int, int> point;
  13. #define X first
  14. #define Y second
  15.  
  16. const double pi = 2*acos(0.0);
  17. int n, R;
  18. vector<point> points;
  19.  
  20. void input() {
  21.     cin>>n>>R;
  22.     points.resize(n);
  23.     int x,y;
  24.     for (int i=0;i<n;i++) {
  25.         cin>>x>>y;
  26.         points[i] = point(x,y);
  27.     }   
  28. }
  29. bool cw(const point &a, const point &b, const point &c) {
  30.     return a.X * (b.Y - c.Y) + b.X * (c.Y - a.Y) + c.X * (a.Y - b.Y) < 0;
  31. }
  32. vector<point> convexHull(vector<point> &p) {
  33.  
  34.     int k = 0;
  35.     sort(p.begin(), p.end());
  36.     vector<point> q(n*2); // ?
  37.     for (int i=0; i<n; q[k++] = p[i++])
  38.         for ( ; k>=2 && !cw(q[k-2],q[k-1],p[i]); --k)
  39.             ;
  40.     for (int i=n-2, t=k; i>=0; q[k++] = p[i--])
  41.         for ( ; k > t && !cw(q[k-2],q[k-1],p[i]); --k)
  42.             ;
  43.     q.resize(k-1 - (q[0] == q[1]));
  44.     return q;
  45. }
  46. double dist(point &a, point &b) {
  47.     return sqrt(0.0 + (a.X - b.X)*(a.X - b.X) + (a.Y - b.Y)*(a.Y - b.Y));
  48. }
  49. void solve() {
  50.     vector<point> hull = convexHull(points);
  51.     double res = 2*pi*R;
  52.     for (int i=0; i<hull.size();++i) {
  53.         res += dist(hull[i], hull[(i+1)%hull.size()]);
  54.     }
  55.     printf("%0.0f",res);
  56. }
  57. int main() {
  58.     freopen("input.txt","r",stdin);
  59.     freopen("output.txt","w",stdout);
  60.     input();
  61.     solve();
  62. }


Editing is locked.