Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define EPS 1e-10
- #define INF 10000
- #define MAXN 10005
- typedef long double ld;
- bool Equals(ld x, ld y) { return fabs(x-y) < EPS; }
- bool BiggerEqual(ld x, ld y) { return fabs(x-y)<EPS || x>y; }
- ld sq(ld a) { return a*a; }
- struct Vect {
- ld x, y;
- Vect(ld a=0, ld b=0) { x=a, y=b; }
- bool operator==(Vect a) { return Equals( x, a.x ) && Equals( y, a.y ); }
- Vect operator+(Vect a) { return Vect(x+a.x,y+a.y); }
- Vect operator-(Vect a) { return Vect(x-a.x,y-a.y); }
- Vect operator*(ld a) { return Vect(x*a,y*a); }
- Vect operator/(ld a) { return Vect(x/a,y/a); }
- Vect Perp() { return Vect(-y,x); }
- ld Length() { return sqrt( sq(x) + sq(y) ); }
- ld Cross(Vect a) { return x*a.y - y*a.x; }
- }p[MAXN];
- struct Seg {
- Vect p1, p2, v;
- Seg(Vect a=Vect(), Vect b=Vect()) { p1=a, p2=b; v=p2-p1; }
- ld OnLeft(Vect a) { return (p1-a).Cross(p2-a); }
- bool Parallel(Seg a) { //Suppose no Seg is (0,0)
- return Equals( v.Cross(a.v), 0); }
- bool containedIn(Seg a) { //Suppose they are parallel
- return BiggerEqual(a.OnLeft(p1), 0); }
- ld intersectionFactor(Seg a) { //Not parallel. p1+v*t = a.p1+a.v*s, Cross a.v to find t
- return -((p1-a.p1).Cross( a.v ) / v.Cross(a.v)); }
- Vect intersectionLine(Seg a) {
- return p1 + v * intersectionFactor(a); }
- Vect Next(Vect a, ld x=-1) { //Vect a is ON our segment, x=1 for next, x=-1 for previous
- return a + v*x; }
- Seg Move(ld r) {
- Vect p = (v.Perp() * r / v.Perp().Length());
- return Seg(p+p1, p+p2); }
- }seg[MAXN], segT[MAXN];
- bool HalfPlaneIntersectionEmpty(int N, Seg seg[]) {
- Vect leftMost(-INF,-INF);
- random_shuffle(seg+4, seg+N+4);
- int lowInd;
- for (int i=4; i<=N+3; ++i) {
- if (BiggerEqual(seg[i].OnLeft(leftMost), 0)) continue; //if leftmost is included in seg[i]
- ld low = -420420511571, high = 420420511571;
- for(int j=0; j<i; ++j) {
- if ( seg[i].Parallel(seg[j]) ) {
- if ( seg[i].containedIn(seg[j]) ) { continue; //nothing happens, or there is no solution
- } else { return true; }}
- Vect inter = seg[i].intersectionLine(seg[j]);
- ld factor = seg[i].intersectionFactor(seg[j]);
- if (BiggerEqual(seg[j].OnLeft( seg[i].Next(inter,-1) ), 0)) {
- high = min(high, factor);
- } else if (low < factor) {
- low = factor;
- lowInd = j; }}
- if ( BiggerEqual(low,high) ) return true;
- leftMost = seg[i].intersectionLine(seg[lowInd]); }
- return false; }
- ld Solve(int N) {
- ld lo=0, hi=INF, mid;
- int ans;
- for(int i=1; i<=50; ++i) {
- mid = (lo+hi)/2;
- for(int j=4; j<=N+3; ++j) {
- segT[j] = seg[j].Move(mid); }
- ans = HalfPlaneIntersectionEmpty(N, segT);
- if (ans) {
- hi = mid; }
- else {
- lo = mid; }}
- return lo; }
- int main() {
- srand(time(NULL));
- int N;
- scanf("%d", &N);
- for(int i=1; i<=N; ++i) {
- scanf("%Lf %Lf", &p[i].x, &p[i].y); }
- seg[0] = segT[0] = Seg( Vect(-INF,INF), Vect(-INF,-INF) );
- seg[1] = segT[1] = Seg( Vect(-INF,-INF), Vect(INF,-INF) );
- seg[2] = segT[2] = Seg( Vect(INF,-INF), Vect(INF,INF) );
- seg[3] = segT[3] = Seg( Vect(INF,INF), Vect(-INF,INF) );
- for(int i=1; i<=N; ++i) {
- seg[i+3] = Seg( p[i], p[(i%N)+1] ); }
- printf("%.3Lf\n", Solve(N)); }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement