codeforces 801 D. Volatile Kite（数学题）

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

题意：求出一个最大值D，使得一个给定的凸多边形任意点移动范围在半径为D的圆中，都不会构成一个凹都边形。

还有给出的多边形的点是按顺时针给出的。

题解：要使的任意点移动都不构成凹多边形，显然只要最极限的移动状态就是相邻的3个点在同一直线上。

于是只要遍历一遍所有的点然后计算出该点到相邻两点构成的直线距离d。D=min(d[i]/2);

所以这题还会用到一个公式点到线的距离

#include <iostream>

#include <cstring>

#include <cmath>

#include <cstdio>

using namespace std;

const int M = 1e3 + 10;

double x[M] , y[M];

double getd(int pos , double a , double b , double c) {

    return abs((a * x[pos] + b * y[pos] + c) / sqrt(a * a + b * b));

}

double cau(int a , int b , int c) {

    double A , B  , C;

    A = (y[b] - y[c]) , B = x[c] - x[b] , C = (x[b] - x[c]) * y[b] - (y[b] - y[c]) * x[b];

    return getd(a , A , B , C);

}

int main() {

    int n;

    scanf("%d" , &n);

    for(int i = 0 ; i < n ; i++) {

        scanf("%lf%lf" , &x[i] , &y[i]);

    }

    double D = 1.0 * 1e12;

    for(int i = 0 ; i < n ; i++) {

        if(i == n - 1) {

            D = min(D , cau(i , i - 1 , 0));

        }

        else if(i == 0) {

            D = min(D , cau(i , n - 1 , 1));

        }

        else {

            D = min(D , cau(i , i - 1 , i + 1));

        }

    }

    printf("%.10lf\n" , D / 2);

    return 0;

}

巴特西

codeforces 801 D. Volatile Kite（数学题）

最新文章

热门文章