(7420) 맹독 방벽

https://www.acmicpc.net/problem/7420

단계별로 풀어보기

51단계(기하 3) 3번째

 

 

 

필요한 최소 방벽 길이는 컨벡스 헐로 구한 볼록다각형의 둘레+반지름이 L인 원의 둘레다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

struct Point{
  long x, y;
  long p, q;
  Point(int x1= 0, int y1= 0): x(x1), y(y1), p(1), q(0) {}
  
  void set(const Point &base){
    p= x-base.x;
    q= y-base.y;
  }

  bool operator <(const Point &A) const {
    if(q*A.p!=p*A.q)  return q*A.p<p*A.q;
    if(p*p+q*q!=A.p*A.p+A.q*A.q)  return p*p+q*q<A.p*A.p+A.q*A.q;
    if(y!=A.y)  return y<A.y;
    return x<A.x;
  }
};

inline long ccw(const Point &p1, const Point & p2, const Point & p3){
  return 1L*(p2.x-p1.x)*(p3.y-p1.y)-1L*(p3.x-p1.x)*(p2.y-p1.y);
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, l;

  cin >> n >> l;

  vector<Point> p(n);
  
  for(int i=0;i<n;i++){
    cin >> p[i].x >> p[i].y;
  }

  sort(p.begin(), p.end());
  for(int i=1;i<n;i++)  p[i].set(p[0]);
  sort(p.begin()+1, p.end());

  stack<int> s;
  s.push(0);  s.push(1);
  
  for(int i=2;i<n;i++){
    while(s.size()>=2){
      int second= s.top();
      s.pop();
      int first= s.top();
        
      if(ccw(p[first],p[second],p[i])>0){
        s.push(second);
        
        break;
      }
    }

    s.push(i);
  }
  
  int sz= s.size();
  vector<int> v;
  v.reserve(sz+1);
  
  while(!s.empty()){
    v.push_back(s.top());
    s.pop();
  }
  v.push_back(v[0]);

  double ans= M_PI*2*l;
  
  for(int i=0;i<sz;i++){
    int dx= p[v[i]].x-p[v[i+1]].x;
    int dy= p[v[i]].y-p[v[i+1]].y;
    
    ans+= sqrt(1L*dx*dx+1L*dy*dy);
  }
  
  cout << round(ans);

  return 0;
}