Codeforces Round #409 (Div. 2) D. Volatile Kite 计算几何、凸多边形、线段类

My Solution

题意：给出一个凸多边形，要求求出一个最大的dist，使得所有的点可以任意移动距离最大为第dist的路程，依然为凸多边形。

计算几何、凸多边形、线段类

对于凸多边形，每相邻的三个点可以构成一个三角形ABC，答案为B到AC的距离的一半，

可以以每个点为圆心话圆，这里借用一下官方Tutorial里的图片☺☺

然后借助下常用的点类和线段类即可，以下用的是红书上的线段类

复杂度 O(n)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e3 + 8;

//error correct
const double EPS = 1e-8;
inline int cmp(double x)
{
    if(fabs(x) < EPS) return 0; if(x > 0) return 1;
    return -1;
}

//point class
const double pi = acos(-1.0);
inline double sqr(double x)
{
    return x * x;
}
struct point{
    double x, y;
    point() {}
    point(double a, double b) : x(a), y(b) {}
    void input(){
        cin >> x >> y;
    }
    friend point operator + (const point &a, const point &b){
        return point(a.x + b.x, a.y + b.y);
    }
    friend point operator - (const point &a, const point &b){
        return point(a.x - b.x, a.y - b.y);
    }
    friend bool operator == (const point &a, const point &b){
        return (cmp(a.x - b.x) == 0) && (cmp(a.y - b.y) == 0);
    }
    friend point operator * (const point &a, const double &b){
        return point(a.x * b, a.y * b);
    }
    friend point operator * (const double &a, const point &b){
        return point(a * b.x, a * b.y);
    }
    friend point operator / (const point &a, const double &b){
        return point(a.x / b, a.y / b);
    }
    double norm(){
        return sqrt(sqr(x) + sqr(y));
    }
};
double det(const point &a, const point &b){
    return a.x * b.y - a.y * b.x;
}//计算2个向量的叉积
double dot(const point &a, const point &b){
    return a.x * b.x + a.y * b.y;
}//计算2个向量的点积
double dist(const point &a, const point &b){
    return (a - b).norm();
}//计算2个点的距离
point rotate_point(const point &p, double A){
    double tx = p.x, ty = p.y;
    return point(tx * cos(A) - ty * sin(A), tx * sin(A) + ty * cos(A));
}//向量op绕原点逆时针旋转A(弧度)

// line class
struct line{
    point a, b;
    line() {}
    line(point x, point y) : a(x), b(y) {}
};
inline line point_make_line(const point &a, const point &b){
    return line(a, b);
}
inline double dis_point_segment(const point &p, const point &s, const point &t){
    if(cmp(dot(p-s, t-s)) < 0) return (p-s).norm();
    if(cmp(dot(p-t, s-t)) < 0) return (p-t).norm();
    return fabs(det(s-p, t-p) / dist(s, t));
}//求p点到线段st的距离
inline void PointProjLine(const point &p, const point &s, const point &t, point &cp){
    double r = dot((t-s), (p-s)) / dot(t-s, t-s);
    cp = s + r*(t-s);
}//求p点到线段st的垂足，保存在cp中
inline bool PointOnSegment(const point &p, const point &s, const point &t){
    return (cmp(det(p-s, t-s)) == 0) && (cmp(dot(p-s, p-t)) <= 0); }//判断p点是否在线段st上 inline bool parallel(const line &a, const line &b){ return !cmp(det(a.a - a.b, b.a - b.b)); }//判断a和b是否平行 inline bool line_make_point(const line &a, const line &b, point &res){ if(parallel(a, b)) return false; double s1 = det(a.a-b.a, b.b-b.a); double s2 = det(a.b-b.a, b.b-b.a); res = (s1*a.b - s2*a.a) / (s1 - s2); return true; }//判断a和b是否相交，如果相交则返回true且交点保存在res中 inline line move_d(const line &a, const double &len){ point d = a.b - a.a; d = d / d.norm(); d = rotate_point(d, pi/2); return line(a.a + d*len, a.b + d*len); }//将直线a沿法向量方向平移距离len得到的直线 point val[MAXN]; int n; inline int mod(int x) { return x - x / n * n; } int main() { #ifdef LOCAL freopen("d.txt", "r", stdin); //freopen("d.out", "w", stdout); int T = 4; while(T--){ #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int i; double ans = 2e9+8; cin >> n;
    for(i = 0; i < n; i++){
        val[i].input();
    }
    for(i = 0; i < n; i++){
        ans = min(ans, dis_point_segment(val[mod(i+1)], val[i], val[mod(i+2)]) / 2);
    }
    cout << fixed << setprecision(10) << ans << endl;


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

Thank you!

                                                                                                                                             ------from ProLightsfx