首页 > 代码库 > CodeForces 801D 计算几何,水

CodeForces 801D 计算几何,水

CodeForces 801D

题意:n个点的凸多边形,如果每个点都可在半径为 r的范围内移动,要保证仍为多边形,问 r最大为多少。

tags:水题,练练手

#include<bits/stdc++.h>using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b)  memset(a,b,sizeof(a))#define INF 0x3f3f3f3f#define MP make_pair#define PB push_back#define fi  first#define se  second#define eps  1e-6typedef long long ll;const int N = 2005;int n;struct Point { double x, y; } p[N];double dis(Point a, Point b){    return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));}double Heron(double a, double b, double c){    double p=(a+b+c)/2;    return sqrt(p*(p-a)*(p-b)*(p-c));}double getsqr(Point a, Point b, Point c){    return Heron(dis(a,b), dis(b,c), dis(a,c));}int main(){    scanf("%d", &n);    rep(i,1,n) scanf("%lf %lf", &p[i].x, &p[i].y);    p[n+1]=p[1], p[n+2]=p[2];    double ans=4.6e18;    rep(i,3,n+2)    {        double len=getsqr(p[i-2], p[i-1], p[i])/dis(p[i-2],p[i]);        ans=min(ans, len);    }    printf("%.6f\n", ans);    return 0;}

CodeForces 801D 计算几何,水