思路：特殊情況，點在一條直線上，求凸包的時候可以檢查出來，n等於1的時候是個特殊情況。
求點到直線的距離，因為點在直線Ax + By + C = 0同側。所以對於任意n個點中的一個點 (X0, Y0) , Ax0 + By0 + C 應該正負號相同。
用直線的一般式就可以用O(1)的時間求一條直線上的距離。
兒童節第二題，哈哈。
[cpp]
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
int n;
struct point {
double x;
double y;
point (double a=0, double b = 0):x(a), y(b){}
};
typedef point Vector;
point operator + (const point &a, const point &b) {
return point(a.x+b.x, a.y+b.y);
}
point operator - (const point &a, const point &b) {
return point(a.x-b.x, a.y-b.y);
}
double det(const point &a, const point &b) {
return a.x*b.y - a.y*b.x;
}
struct polygon_convex {
vector <point> P;
polygon_convex(int Size = 0) {
P.resize(Size);
}
};
const double eps = 1e-10;
int dcmp(double x) {
if(fabs(x)<eps) return 0;
if(x > 0) return 1;
return -1;
}
bool comp_less(const point &a, const point &b) {
return dcmp(a.x-b.x)<0 || (dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)<0);
}
bool cmpx(const point &a, const point &b) {
if(dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0) return true;
return false;
}
polygon_convex convex_hull(vector<point> a) {
polygon_convex res(2*a.size()+5);
sort(a.begin(), a.end(), comp_less);
a.erase(unique(a.begin(), a.end(), cmpx), a.end());
int m = 0;
for(int i = 0; i < int(a.size()); ++i) {
while(m>1 && dcmp(det(res.P[m-1]-res.P[m-2], a[i]-res.P[m-2]))<=0)
--m;
res.P[m++] = a[i];
}
int k = m;
for(int i = int(a.size())-2; i >= 0; --i) {
while(m>k && dcmp(det(res.P[m-1]-res.P[m-2], a[i]-res.P[m-2]))<=0)
--m;
res.P[m++] = a[i];
}
res.P.resize(m);
if(a.size()>1) res.P.resize(m-1);
return res;
}
vector <point> tmp;
double sumx = 0, sumy = 0;
double ans = 0;
void init() {
sumx = 0, sumy = 0;
tmp.clear();
ans = 1e100;
}
//Ax + By + C = 0;
double get(double A, double B, double C) {
double k = fabs(A*sumx + B*sumy + n*C); //剛開始也沒考慮到。
double v = sqrt(A*A + B*B);//v != 0;
return k/v;
}
double getDist(const point &a, const point &b) {
double A = a.y-b.y;
double B = b.x-a.x;
double C = a.x*b.y - a.y*b.x;
return get(A, B, C);
}
int main()
{
int counter = 0;
int T;
point t;
scanf("%d", &T);
while(T--) {
init();
scanf("%d", &n);
for(int i = 0; i < n; i++) {
scanf("%lf%lf", &t.x, &t.y);
sumx += t.x; sumy += t.y;
tmp.push_back(t);
}
polygon_convex tres = convex_hull(tmp);
int Size = (int)tres.P.size();
printf("Case #%d: ", ++counter);
if(Size == 2 || Size == 1) { //剛開始wa一次，看了看題目n>0.又把n=1考慮一下。
printf("0.000\n");
continue;
}
for(int i = 0; i < Size; i++) {
double temp = getDist(tres.P[i], tres.P[(i+1)%Size]);
ans = min(ans, temp);
}
printf("%.3lf\n", ans/n);
}
return 0;
}
