【codeforces 801D】Volatile Kite

【题目链接】:http://codeforces.com/contest/801/problem/D

【题意】



给你一个凸多边形的n个点;

然后允许你将每个点移动到距离不超过D的范围内;

要求无论如何移动这n个点始终形成凸多边形;

问D最大为多少;

【题解】





如上图

是相邻的3个点(顺时针)

则我们要在(x1,y1)到直线(x0,y0)->(x2,y2)的距离的二分之一

即

1/2Di中取最小值

因为如果D再大一点

连成的l1和l2就会出现

l2在l1的另外一侧的情况;

而这就使得边l2的两侧都有边->不符合凸多边形的定义;

如下图;





【Number Of WA】



0



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 1100;

struct abc

{

    long double x,y;

};

int n;

abc a[N];

long double ans = -1;

long double get_ans(abc a0,abc a1,abc a2)

{

    long double x0 = a0.x,y0 = a0.y;

    long double x1 = a1.x,y1 = a1.y;

    long double x2 = a2.x,y2 = a2.y;

    long double dy = y2-y0,dx = x2-x0;

    long double A = -dy,B = dx,C = dy*x0-dx*y0;

    return ((A*x1+B*y1+C)/sqrt(A*A+B*B))/2.0;

}

int main()

{

    //freopen("F:\\rush.txt","r",stdin);

    ios::sync_with_stdio(false);

    cin >> n;

    rep1(i,1,n)

        cin >> a[i].x>>a[i].y;

    a[n+1] = a[1],a[n+2] = a[2];

    rep1(i,1,n)

    {

        if (ans<0)

            ans = get_ans(a[i],a[i+1],a[i+2]);

        else

            ans = min(ans,get_ans(a[i],a[i+1],a[i+2]));

    }

    cout << fixed << setprecision(10) << ans << endl;

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}