VK Cup 2017 B. Volatile Kite （Div . 1）（凸多边形退化）（计算几何）

叁歲伎倆 2022-06-17 05:13 163阅读 0赞

题目链接：

[点击打开链接][Link 1]

http://codeforces.com/contest/801/problem/D

题意：

给定一个凸n边形，你可以移动每个点在x范围之内，问你x最大为多少时，这个n边形仍为凸边形? 即不能退化为凹多边形。

题解：

如果想要一个凸多边形不退化为凹多边形，当一个点A和它相连的两个点B、 C退化为成一条直线的时候就不行了，那么在极限的情况下，任意的相邻的三个点必然最多形成一条直线。因此我们可以求出点 i - 1和 i + 1的直线向量，再求点 i到这条直线的距离，再除以2，其实就是三角形的高 / 2。再取这些答案中最小的一个值。

AC代码：

#pragma comment(linker, "/STACK:102400000,102400000")
    #include <bits/stdc++.h>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <iostream>
    #include <cstring>
    #include <vector>
    #include <map>
    #include <cmath>
    #include <queue>
    #include <set>
    #include <bitset>
    #include <iomanip>
    #include <list>
    #include <stack>
    #include <utility> 
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    typedef vector<int> vi;
    const double eps = 1e-8;  
    const int INF = 1e9+7; 
    const ll inf =(1LL<<62) ;
    const int MOD = 1e9 + 7;  
    const ll mod = (1LL<<32);
    const int N =1e6+6; 
    const int M=100010;
    const int maxn=1001;
    #define mst(a) memset(a, 0, sizeof(a))
    #define M_P(x,y) make_pair(x,y)
    #define pi acos(-1.0)
    #define in freopen("in.txt","r",stdin) 
    #define rep(i,j,k) for (int i = j; i <= k; i++)  
    #define per(i,j,k) for (int i = j; i >= k; i--)  
    #define lson x << 1, l, mid  
    #define rson x << 1 | 1, mid + 1, r  
    const int lowbit(int x) { return x&-x; }
    int read(){ int v = 0, f = 1;char c =getchar();
    while( c < 48 || 57 < c ){if(c=='-') f = -1;c = getchar();}
    while(48 <= c && c <= 57) v = v*10+c-48, c = getchar();
    return v*f;}
    map<int,int>mp;
    
    struct Point
    {
        double x,y;
        Point(double x=0,double y=0):x(x),y(y) {}
    }p[1000010];
    
    typedef Point point;
    
    point operator -(Point a,Point b)
    {
        return point(a.x-b.x,a.y-b.y);
    }
    point operator +(Point a,Point b)
    {
        return point(a.x+b.x,a.y+b.y);
    }
    point operator *(Point a,double t)
    {
        return point(a.x*t,a.y*t);
    }
    point operator /(Point a,double t)
    {
        return point(a.x/t,a.y/t);
    }
    bool operator < (const Point &a,const Point &b)
    {
        return a.y<b.y || (fabs(a.y-b.y)<=eps && a.x<b.x);
    }
    bool operator == (const Point &a,const Point &b)
    {
        if(fabs(a.x-b.x)<=eps && fabs(a.y-b.y)<=eps)
            return true;
        return false;
    }
    int dcmp(double x)
    {
        if(fabs(x)<=eps) return 0;
        return x<0?-1:1;
    }
    
    double dot(point a,point b) //点积
    {
        return a.x*b.x+a.y*b.y;
    }
    double cross(Point a,Point b) //叉积
    {
        return a.x*b.y-a.y*b.x;
    }
    /*两点之间的距离*/
    double disn(Point a,Point b)
    {
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
        
    }
    double lentgh(Point a)//向量长度
    {
        return sqrt(dot(a,a));
    }
    double vec_angle(point a,point b)//两向量夹角
    { 
        return acos(dot(a,b)/lentgh(a)/lentgh(b));
    }
    /*  
    点到直线的距离
    若不取绝对值 表示有向距离
    */
    double distance(Point p,Point a,Point b)
    {
        point v1=b-a;
        point v2=p-a;
        return fabs(cross(v1,v2))/lentgh(v1);
        
    }
     /*点到线段的距离*/
    double distancetoseg(Point p,Point a,Point b)
    {
        if(a==b) return lentgh(p-a);
        point v1=b-a;
        point v2=p-a;
        point v3=p-b;
        if(dcmp(dot(v1,v2))<0)
            return lentgh(v2);
        else if(dcmp(dot(v1,v3))>0)
            return lentgh(v3);
        else
            return fabs(cross(v1,v2))/lentgh(v1);
       
    }
    
    int n;
    int main()
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; ++i) scanf("%lf%lf",&p[i].x,&p[i].y);
        double ans = inf;
        for(int i=1;i<=n;i++)
    	{
            int last = i-1;
            int Next = i+1;
            if(last == 0) last = n;
            if(Next==n+1) Next = 1;
            ans = min(distancetoseg(p[i],p[Next],p[last])/2.0,ans);
    	}
        printf("%.10f\n",ans);
        return 0;
    }

[Link 1]: http://codeforces.com/contest/801/problem/D