Advertisement
Guest User

Untitled

a guest
Jun 25th, 2018
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.26 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define EPS 1e-10
  4. #define INF 10000
  5. #define MAXN 10005
  6. typedef long double ld;
  7.  
  8. bool Equals(ld x, ld y) { return fabs(x-y) < EPS; }
  9. bool BiggerEqual(ld x, ld y) { return fabs(x-y)<EPS || x>y; }
  10. ld sq(ld a) { return a*a; }
  11.  
  12. struct Vect {
  13.   ld x, y;
  14.   Vect(ld a=0, ld b=0) { x=a, y=b; }
  15.   bool operator==(Vect a) { return Equals( x, a.x ) && Equals( y, a.y ); }
  16.   Vect operator+(Vect a) { return Vect(x+a.x,y+a.y); }
  17.   Vect operator-(Vect a) { return Vect(x-a.x,y-a.y); }
  18.   Vect operator*(ld a) { return Vect(x*a,y*a); }
  19.   Vect operator/(ld a) { return Vect(x/a,y/a); }
  20.   Vect Perp() { return Vect(-y,x); }
  21.   ld Length() { return sqrt( sq(x) + sq(y) ); }  
  22.   ld Cross(Vect a) { return x*a.y - y*a.x; }
  23. }p[MAXN];
  24.  
  25. struct Seg {
  26.   Vect p1, p2, v;
  27.   Seg(Vect a=Vect(), Vect b=Vect()) { p1=a, p2=b; v=p2-p1; }
  28.   ld OnLeft(Vect a) { return (p1-a).Cross(p2-a); }
  29.   bool Parallel(Seg a) { //Suppose no Seg is (0,0)
  30.     return Equals( v.Cross(a.v), 0);   }
  31.   bool containedIn(Seg a) { //Suppose they are parallel
  32.     return BiggerEqual(a.OnLeft(p1), 0);   }
  33.   ld intersectionFactor(Seg a) { //Not parallel. p1+v*t = a.p1+a.v*s, Cross a.v to find t
  34.     return -((p1-a.p1).Cross( a.v ) / v.Cross(a.v));   }
  35.   Vect intersectionLine(Seg a) {
  36.     return p1 + v * intersectionFactor(a);   }
  37.   Vect Next(Vect a, ld x=-1) { //Vect a is ON our segment, x=1 for next, x=-1 for previous
  38.     return a + v*x;   }
  39.   Seg Move(ld r) {
  40.     Vect p = (v.Perp() * r / v.Perp().Length());
  41.     return Seg(p+p1, p+p2);   }
  42. }seg[MAXN], segT[MAXN];
  43.  
  44. bool HalfPlaneIntersectionEmpty(int N, Seg seg[]) {
  45.   Vect leftMost(-INF,-INF);
  46.   random_shuffle(seg+4, seg+N+4);
  47.   int lowInd;
  48.  
  49.   for (int i=4; i<=N+3; ++i) {
  50.     if (BiggerEqual(seg[i].OnLeft(leftMost), 0)) continue; //if leftmost is included in seg[i]
  51.  
  52.     ld low = -420420511571, high = 420420511571;
  53.     for(int j=0; j<i; ++j) {
  54.       if ( seg[i].Parallel(seg[j]) ) {
  55.     if ( seg[i].containedIn(seg[j]) ) { continue; //nothing happens, or there is no solution
  56.     } else { return true;   }}
  57.  
  58.       Vect inter = seg[i].intersectionLine(seg[j]);
  59.       ld factor = seg[i].intersectionFactor(seg[j]);
  60.       if (BiggerEqual(seg[j].OnLeft( seg[i].Next(inter,-1) ), 0)) {
  61.     high = min(high, factor);
  62.       } else if (low < factor) {
  63.     low = factor;    
  64.     lowInd = j;   }}
  65.  
  66.     if ( BiggerEqual(low,high) ) return true;
  67.     leftMost = seg[i].intersectionLine(seg[lowInd]);   }
  68.  
  69.   return false;   }
  70.  
  71. ld Solve(int N) {
  72.   ld lo=0, hi=INF, mid;
  73.   int ans;
  74.   for(int i=1; i<=50; ++i) {
  75.     mid = (lo+hi)/2;
  76.     for(int j=4; j<=N+3; ++j) {
  77.       segT[j] = seg[j].Move(mid); }
  78.     ans = HalfPlaneIntersectionEmpty(N, segT);
  79.    
  80.     if (ans) {
  81.       hi = mid;   }
  82.     else {
  83.       lo = mid;   }}
  84.   return lo;   }
  85.  
  86. int main() {
  87.   srand(time(NULL));
  88.   int N;
  89.   scanf("%d", &N);
  90.   for(int i=1; i<=N; ++i) {
  91.     scanf("%Lf %Lf", &p[i].x, &p[i].y);  }
  92.   seg[0] = segT[0] = Seg( Vect(-INF,INF), Vect(-INF,-INF) );
  93.   seg[1] = segT[1] = Seg( Vect(-INF,-INF), Vect(INF,-INF) );
  94.   seg[2] = segT[2] = Seg( Vect(INF,-INF), Vect(INF,INF) );
  95.   seg[3] = segT[3] = Seg( Vect(INF,INF), Vect(-INF,INF) );  
  96.   for(int i=1; i<=N; ++i) {
  97.     seg[i+3] = Seg( p[i], p[(i%N)+1] );   }  
  98.   printf("%.3Lf\n", Solve(N));   }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement