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.     int N;
  8.     if(!(cin >> N)) return 0;
  9.     vector<pair<double,double>> pts(N);
  10.     for(int i=0;i<N;i++) cin >> pts[i].first >> pts[i].second;
  11.     double xA,yA,xB,yB;
  12.     cin >> xA >> yA >> xB >> yB;
  13.  
  14.     auto cross = [](double ax,double ay,double bx,double by){
  15.         return ax*by - ay*bx;
  16.     };
  17.     auto dot = [](double ax,double ay,double bx,double by){
  18.         return ax*bx + ay*by;
  19.     };
  20.  
  21.     double wx = xB - xA, wy = yB - yA;
  22.     double r = hypot(wx, wy);
  23.     // 문제 보장상 A != B 이므로 r > 0
  24.     double ux = wx / r, uy = wy / r;
  25.  
  26.     const double EPS = 1e-12;
  27.     long double total = 0.0L;
  28.  
  29.     for (int i=0;i<N;i++){
  30.         double vx = pts[i].first  - xA;
  31.         double vy = pts[i].second - yA;
  32.         double d = hypot(vx, vy);
  33.         double c = cross(vx, vy, wx, wy);            // v x w
  34.         bool inDisk = (d <= r + EPS);
  35.         bool inHalf = (c >= -EPS); // 경계 포함
  36.  
  37.         if (inDisk && inHalf) {
  38.             // 이미 반원 안
  39.             continue;
  40.         }
  41.  
  42.         double best = 1e100;
  43.  
  44.         // 후보 1: 원 밖 + 왼쪽이면 원으로의 반지름 투영
  45.         if (d > r + EPS && c > EPS) {
  46.             best = min(best, d - r);
  47.         }
  48.  
  49.         // 후보 2/3: 반평면 경계선(직선 ℓ)로의 투영
  50.         double t = dot(vx, vy, ux, uy);          // v · u (직선 방향 성분)
  51.         double d_perp = fabs(cross(vx, vy, ux, uy)); // 선까지의 수직거리 (u가 단위벡터)
  52.         if (t >= -r - EPS && t <= r + EPS) {
  53.             // 지름 선분 안으로 수직 낙하
  54.             best = min(best, d_perp);
  55.         } else {
  56.             // 지름 끝점 두 개 중 가까운 곳
  57.             double parallel_excess = fabs(t) - r; // >= 0
  58.             if (parallel_excess < 0) parallel_excess = 0; // 안정화
  59.             double cand = hypot(parallel_excess, d_perp);
  60.             best = min(best, cand);
  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 5316KB
comments (?)
stdin
copy 
3
0 2
3 2
3 4
2 2 2 3
stdout
copy 
3.2360679775
https://ideone.com/etTegb
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!