fork download
copy 
  1. /*
  2. ID: toooooEasy or RafaelSaddatimov
  3. PROG:
  4. */
  5. #include <bits/stdc++.h>
  6. #define MAX 10009
  7. #define MOD 1000000007
  8. #define INF 2100000000
  9. #define EPS 1e-6
  10. #define ll long long
  11. #define _l long
  12. #define F first
  13. #define S second
  14. #define NLINE printf("\n")
  15. #define BYE(v) return 0 * printf(v)
  16. #define all(v) v.begin(), v.end()
  17. using namespace std;
  18. _l double A[MAX], B[MAX], C[MAX];
  19. int n, cnt = 0;
  20.  
  21. _l double compute(_l double x, _l double y)
  22. {
  23.     _l double ans = -40000000000.0;
  24.     for(int i=1; i<=n; ++i)
  25.         ans = max(ans, fabs(A[i] * x + B[i] * y + C[i]) / sqrt(A[i] * A[i] + B[i] * B[i])), ++cnt;
  26.     return ans;
  27. }
  28. int main()
  29. {
  30.     //freopen("36", "r", stdin);
  31.     scanf("%d", &n);
  32.     for(int i=1; i<=n; ++i) {
  33.         _l double x1, y1, x2, y2;
  34.         scanf("%Lf%Lf%Lf%Lf", &x1, &y1, &x2, &y2);
  35.         A[i] = y1 - y2;
  36.         B[i] = x2 - x1;
  37.         C[i] = x1 * y2 - y1 * x2;
  38.     }
  39.     _l double l1 = -1000000000.0000, r1 = 1000000000.0000, l2, r2;
  40.     while(r1 - l1 > EPS) {
  41.         _l double m1 = l1 + (r1 - l1) / 3;
  42.         _l double m2 = r1 - (r1 - l1) / 3;
  43.         l2 = -1000000000.0000;
  44.         r2 = 1000000000.0000;
  45.         while(r2 - l2 > EPS) {
  46.             _l double m1_ = l2 + (r2 - l2) / 3;
  47.             _l double m2_ = r2 - (r2 - l2) / 3;
  48.             _l double a1_ = compute(m1, m1_);
  49.             _l double a2_ = compute(m1, m2_);
  50.             if(a1_ < a2_)
  51.                 r2 = m2_;
  52.             else
  53.                 l2 = m1_;
  54.         }
  55.         _l double a1 = compute(m1, l2);
  56.         l2 = -1000000000.0000;
  57.         r2 = 1000000000.0000;
  58.         while(r2 - l2 > EPS) {
  59.             _l double m1_ = l2 + (r2 - l2) / 3;
  60.             _l double m2_ = r2 - (r2 - l2) / 3;
  61.             _l double a1_ = compute(m2, m1_);
  62.             _l double a2_ = compute(m2, m2_);
  63.             if(a1_ < a2_)
  64.                 r2 = m2_;
  65.             else
  66.                 l2 = m1_;
  67.         }
  68.         _l double a2 = compute(m2, l2);
  69.         if(a1 < a2)
  70.             r1 = m2;
  71.         else
  72.             l1 = m1;
  73.     }
  74.     printf("%.13Lf %.13Lf\n", l1, l2);
  75. }
Success #stdin #stdout 0s 15696KB
comments (?)
stdin
copy 
2
-10000 10000 10000 10000
-10000 -10000 10000 -9999
stdout
copy 
399990000.0057771150023 9999.9999999050897
https://ideone.com/h8Vl7K
language:
C++14 (gcc 8.3)
created:
6 years 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!