[几何] Codeforces 772B VK Cup 2017 - Round 2 B. Volatile Kite

那么问题来了 O(n)判到底对不对

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef double ld;

struct P{
  ld x,y;
  void read() { double _x,_y; scanf("%lf%lf",&_x,&_y); x=_x; y=_y; }
  P(ld x=0,ld y=0):x(x),y(y) { }
  P rot(ld A){ return P(x*cos(A)-y*sin(A),x*sin(A)+y*cos(A)); }
  ld dist(){ return sqrt(x*x+y*y); }
  friend P operator + (P A,P B) { return P(A.x+B.x,A.y+B.y); }
  friend P operator - (P A,P B) { return P(A.x-B.x,A.y-B.y); }
  friend ld operator * (P A,P B) { return A.x*B.y-B.x*A.y; }
  friend P operator * (P A,ld B) { return P(A.x*B,A.y*B); }
  friend P operator / (P A,ld B) { return P(A.x/B,A.y/B); }
  friend ld dist(P A,P B){ return (A-B).dist(); }
}p[1005];
int n;

inline ld solve(P A,P B,P C){
  return fabs((A-C)*(B-C))/((B-A).dist());
}

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  scanf("%d",&n);
  for (int i=0;i<n;i++) p[i].read();
  ld ans=1e15;
  for (int i=0;i<n;i++)
    ans=min(ans,solve(p[(i+n-1)%n],p[(i+1)%n],p[i]));
  printf("%.10lf\n",ans/2);
  return 0;
}