Submission #38433391

---

Source Code Expand

#include <bits/stdc++.h>
template<class T>
using Point = std::pair<T, T>;

template<class T>
class ConvexHull{
public:
  std::vector<Point<T>> lower;
  std::vector<Point<T>> upper;
  Point<T> sub(Point<T> a,Point<T> b){ // return a-b
    return {a.first - b.first,a.second-b.second};
  }
  T cross(Point<T> a, Point<T> b, Point<T> c){ // (a-b) x (c-b)
    auto [x0,y0] = sub(a,b);
    auto [x1,y1] = sub(c,b);
    return x1*y0 -x0*y1;
  }
  ConvexHull(): lower{}, upper{}{}
  ConvexHull(Point<T> p): lower{p}, upper{p}{}
  ConvexHull(std::vector<Point<T>>&p) {
    sort(p.begin(),p.end());
    {
      std::vector<Point<T>> v=p; // 逆时针弧
      for(Point<T>p : v){
        while(lower.size() >= 2 && cross(lower.rbegin()[1], lower.back(), p) <= 0) lower.pop_back();
        lower.push_back(p);
      }
    }
    {
      std::vector<Point<T>> v=p; // 顺时针弧
      for(Point<T>p : v){
        while(upper.size() >= 2 && cross(upper.rbegin()[1], upper.back(), p) >= 0) upper.pop_back();
        upper.push_back(p);
      }
    }
  }
  ConvexHull(const ConvexHull<T>& a, const ConvexHull<T>& b){ // 两个凸包合并
    {
      std::vector<Point<T>> v; // 逆时针弧
      std::merge(a.lower.begin(), a.lower.end(), b.lower.begin(), b.lower.end(), back_inserter(v)); // 本身a,b下标有序, merge 会按pair的比较的排序
      for(Point<T> p : v){
        while(lower.size() >= 2 && cross(lower.rbegin()[1], lower.back(), p) <= 0) lower.pop_back();
        lower.push_back(p);
      }
    }
    {
      std::vector<Point<T>> v; // 顺时针弧
      std::merge(a.upper.begin(), a.upper.end(), b.upper.begin(), b.upper.end(), back_inserter(v)); // 本身a,b下标有序, merge 会按pair的比较的排序
      for(Point<T> p : v){
        while(upper.size() >= 2 && cross(upper.rbegin()[1], upper.back(), p) >= 0) upper.pop_back();
        upper.push_back(p);
      }
    }
  }
};
// -- template --
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

ll read(){ll r;scanf("%lld",&r);return r;}
pair<ll,ll> xy[100010];
double dis(const pair<ll,ll> &p0,const pair<ll,ll>&p1){
  ll dx=p0.first-p1.first;
  ll dy=p0.second-p1.second;
  return sqrt(dx*dx+dy*dy);
}

int main(){
  int n=read();
  rep(i,0,n) {
    xy[i]={read(),read()};
  }
  xy[n]={read(),read()}; // S
  xy[n+1]={read(),read()}; // T
  vector<ConvexHull<ll>> S;
  rep(i,0,n+2) S.push_back(xy[i]);
  while(S.size() > 1){
    rep(i,0,S.size()/2) S[i] = ConvexHull<ll>(S[i*2],S[i*2+1]);
    if(S.size() & 1) S[S.size()/2] = S.back();
    S.resize((S.size()+1)/2);
  }
  assert(S[0].lower[0] == S[0].upper[0]);
  assert(S[0].lower.back() == S[0].upper.back());
  vector<pair<ll,ll> > convex;
  rep(i,0,S[0].lower.size()) convex.push_back(S[0].lower[i]);
  per(i,1,S[0].upper.size()-1) convex.push_back(S[0].upper[i]);

  auto inconvex = [&](const pair<ll,ll> p) -> int{
    rep(i,0,size(convex)) if(convex[i]==p) return i;
    return -1;
  };

  int s_i = inconvex(xy[n]);
  int t_i = inconvex(xy[n+1]);
  int sz=size(convex);
  if(s_i != -1 and t_i != -1){
    double ans0 = 0;
    rep(i,1,size(convex)){
      int i0=(s_i+i-1)%size(convex);
      int i1=(s_i+i)%size(convex);
      ans0 += dis(convex[i0],convex[i1]);
      if(i1==t_i) break;
    }
    double ans1 = 0;
    rep(i,1,size(convex)){
      int i0=(sz+s_i-i+1)%sz;
      int i1=(sz+s_i-i)%sz;
      ans1 += dis(convex[i0],convex[i1]);
      if(i1==t_i) break;
    }
    printf("%.15lf\n",min(ans0,ans1));
  }else{
    printf("%.15lf\n", dis(xy[n],xy[n+1]));
  }
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:63:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   63 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result