# 某岛

… : "…アッカリ～ン . .. . " .. .
May 26, 2012

## POJ 3525. Most Distant Point from the Sea

### Analysis :

。。。貌似正解是二分+半平面交判定？。。（

1. 无差别360°随即产生一个。。。
2. 对多边形扫一遍加权产生一个。。。

。。。于是我的策略是 优先采用 策略 1. 。。。当判定出界的情况下下次采用策略 2.。。）

const int N = 109, L = 200, W = 1000, _T = 3000;
const DB V = 0.8;

// L: 迭代次数
// W: 可分配权值
// _T: 初始温度。。

// V: 降火速率。。

struct Polygon;
DB dist_sqr(Polygon, Po);

struct Polygon{
Po P[N]; int n;

DB dist_sqr(Po p){
return ::dist_sqr((*this), p);
}

void init(int _n){
n = _n; REP(i, n) P[i].input(); P[n] = P[0];
}

bool inside(Po p){
REP(i, n) if (det(P[i], P[i+1], p) < 0) return false;
return true;
}

void solve(){

Po res; int l = 0; REP(i, n){
int w = rand() % W + 1;
res += w * P[i], l += w;
}

res /= l;

DB T = _T, best = dist_sqr(res);

while (T > EPS){

bool improved = false;
bool hard = false;

Po pre = res, cur; DO_C(L){
if (!hard){
DB theta = (DB) (rand() % W) / W * (2*PI);
cur = pre + Po(cos(theta), sin(theta)) * T;
}
else {

Po dir; REP(i, n){
int w = rand() % W + 1;
dir += (P[i] - pre) * w;
}

if (sgn(dir.length_sqr()) == 0) continue;
if (dice()) dir = - dir;

dir /= dir.length(), dir *= T;
cur = pre + dir;
}

if (inside(cur)){
DB temp = dist_sqr(cur);
if (temp > best){
improved = true;
res = cur, best = temp;
}
hard = false;
}
else
hard = true;
}

if (!improved) T *= V;
}

OT(sqrt(best));
}
} P;

DB dist_sqr(Polygon Poly, Po p){
DB res = OO; REP(i, Poly.n) res = min(res, dist_sqr(Seg(Poly.P[i], Poly.P[i+1]), p));
return res;
}

int n;

int main(){

#ifdef LOCAL
freopen("in.txt", "r", stdin);
#endif

while (true){
if (!_RD(n)) break;
P.init(n); P.solve();
}
}