codeforces 613A. Peter and Snow Blower

题目链接

给一个多边形， 一个多边形外的定点， 求这个点距离多边形的最短距离和最长距离。

最长距离肯定是和某个顶点的连线， 而最短距离是和点的连线或是和某条边的连线。

对于一条边上的两个点a, b, 以及外面的定点p， 如果pab构成的三角形， <pab 或者<pba 是钝角， 那么最短距离是离点的最短距离， 否则是离边的。  离边的距离可以根据三角形面积算， 三角形面积可以用海伦公式算。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

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

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-;

const int mod = 1e9+;

const int inf = ;

const int dir[][] = { {-, }, {, }, {, -}, {, } };

double dis(pll a, pll b) {

    return 1.0*(a.first-b.first)*(a.first-b.first)+1.0*(a.second-b.second)*(a.second-b.second);

}

double get(pll a, pll b, pll c) {

    double l1 = dis(a, b);

    double l2 = dis(b, c);

    double l3 = dis(a, c);

    if(l1>=l2+l3)

        return l2;

    if(l2>=l1+l3)

        return l1;

    l1 = sqrt(l1), l2 = sqrt(l2), l3 = sqrt(l3);

    double p = l1+l2+l3;

    p/=;

    double s = sqrt(p*(p-l1)*(p-l2)*(p-l3));

    double ret = s*/l3;

    return ret*ret;

}

pll b[];

int main()

{

    int n, x, y, x1, y1;

    double minn = 1e12, maxx = ;

    cin>>n>>x>>y;

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

        scanf("%d%d", &b[i].fi, &b[i].se);

    }

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

        minn = min(minn, get(b[i], mk(x, y), b[(i+)%n]));

        maxx = max(maxx, dis(mk(x, y), b[i]));

    }

    double ans = (maxx-minn)*PI;

    printf("%.8f", ans);

    return ;

}