fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     int N;
  9.     if (!(cin >> N)) return 0;
  10.     vector<pair<double,double>> pts(N);
  11.     for (int i = 0; i < N; ++i) cin >> pts[i].first >> pts[i].second;
  12.  
  13.     double xA, yA, xB, yB;
  14.     cin >> xA >> yA >> xB >> yB;
  15.  
  16.     auto cross = [](double ax,double ay,double bx,double by){
  17.         return ax*by - ay*bx;
  18.     };
  19.     auto dot = [](double ax,double ay,double bx,double by){
  20.         return ax*bx + ay*by;
  21.     };
  22.  
  23.     // 기본 벡터/반지름/단위방향
  24.     double wx = xB - xA, wy = yB - yA;
  25.     double r = hypot(wx, wy);
  26.     double ux = wx / r,  uy = wy / r; // 단위방향 (A->B)
  27.  
  28.     const double EPS = 1e-12;
  29.     long double total = 0.0L;
  30.  
  31.     for (int i = 0; i < N; ++i) {
  32.         double vx = pts[i].first  - xA;   // v = P - A
  33.         double vy = pts[i].second - yA;
  34.  
  35.         double d = hypot(vx, vy);                 // |v|
  36.         double c = cross(wx, wy, vx, vy);         // ★ 왼쪽 판정: cross(B-A, P-A)
  37.         bool inDisk = (d <= r + EPS);
  38.         bool inHalf = (c >= -EPS);                // 경계 포함
  39.  
  40.         if (inDisk && inHalf) continue;           // 이미 반원 안
  41.  
  42.         double best = 1e100;
  43.  
  44.         // 후보 1) 원 밖 + 왼쪽이면: 원호까지의 최단거리 = d - r (방사투영)
  45.         if (d > r + EPS && c > EPS) {
  46.             best = min(best, d - r);
  47.         }
  48.  
  49.         // 후보 2/3) 지름 선분까지의 거리 (반평면 경계선 = A + t*u, |t| <= r 로 제한)
  50.         double t = dot(vx, vy, ux, uy);                 // 평행 성분
  51.         double d_perp = fabs(cross(vx, vy, ux, uy));    // 직선까지 수직거리 (u 단위)
  52.  
  53.         if (t >= -r - EPS && t <= r + EPS) {
  54.             // 선분 내부로 수직 투영 가능
  55.             best = min(best, d_perp);
  56.         } else {
  57.             // 선분 밖이면 가까운 끝점(A ± r*u)
  58.             double parallel_excess = fabs(t) - r;
  59.             if (parallel_excess < 0) parallel_excess = 0; // 안정화
  60.             best = min(best, hypot(parallel_excess, d_perp));
  61.         }
  62.  
  63.         total += best;
  64.     }
  65.  
  66.     cout.setf(std::ios::fixed);
  67.     cout << setprecision(10) << (double)total << "\n";
  68.     return 0;
  69. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
3
0 2
3 2
3 4
2 2 2 3
stdout
copy 
3.4142135624
https://ideone.com/G3I2c3
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!