題目：一個任意多邊形，判斷是否能放入一個半徑為r的圓
一開始以為是半平面交，果斷看大家的提交時間和代碼長度就不像是，不過還是提交了一發，果斷WA.
後來被昀昀科普了，凹多邊形是不可以這麼求的。凹多邊形可能沒有核，向內推近r後求核，顯然是不對的。
點不是很多，那就只有模擬退火了，貌似不是只有。。。
要寫這題，首先還得寫個判斷點是否在多邊形內，因為以前寫得太矬，打算重新寫一個，然後就折騰了一晚上，各種錯誤，老是用直線去代替線段。有了這個判斷，便可以開始模擬退火
模擬退火關鍵問題在於火候怎麼把握，一開始嘗試選取n個點，步長每次減小1/10，精度控制在1e-3,竟然TLE，看了網上的代碼，也是這麼多。然後開始各種嘗試，果斷減小選取的點數。各種WA,TLE無語。。。
有位好心的ACMER，給了一組數據
4
0 0
0 2
2 2
2 0
1
一般如果在判斷的時候要求精度太高的話，這組數據過不了，果斷不原本1e-8的精度改成1e-3，一通亂改之後，可以說是勉強通過了這組數據。
大清早的起來又是刷屏，各種嘗試火候，最終還是刷進了200ms
最多選 20個點，每個點走5步，步長為原來的0.55，之前的TLE主要原因就是那組數據出不來，而且會WA。
[cpp]
#include<iostream>
#include<fstream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<vector>
#include<ctime>
#include<sstream>
#include<cassert>
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define inf 1<<30
#define N 20
#define pi acos(-1.0)
using namespace std;
struct Point{
double x,y;
double val;
}p[100],tp[100],pre,cur;
struct Segment{
Point a,b;
};
int n;
inline double xmul(Point p0,Point p1,Point p2){
return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}
inline double dist(Point p1,Point p2){
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
//求點到線段距離
inline double Dist_Point_Seg(Point p,Point a,Point b){
Point t=p;
t.x+=a.y-b.y;t.y+=b.x-a.x;
if(xmul(a,t,p)*xmul(b,t,p)>eps)
return dist(p,a)+eps<dist(p,b)?dist(p,a):dist(p,b);
else
return fabs(xmul(p,a,b))/dist(a,b);
}
inline bool online(Point p1,Point p2,Point p){
if(zero(xmul(p1,p2,p))&&((p.x-p1.x)*(p.x-p2.x)<eps&&(p.y-p1.y)*(p.y-p2.y)<eps))
return true;
return false;
}
inline bool across(Segment s1,Segment s2){
if(xmul(s1.a,s1.b,s2.a)*xmul(s1.a,s1.b,s2.b)<eps)
if(xmul(s2.a,s2.b,s1.a)*xmul(s2.a,s2.b,s1.b)<eps)
return true;
return false;
}
inline bool Parallel(Segment s1,Segment s2){
return zero((s1.a.x-s1.b.x)*(s2.a.y-s2.b.y)-(s2.a.x-s2.b.x)*(s1.a.y-s1.b.y));
}
//判斷點是否在多邊形內
inline bool In_Polygon(Point cen){
int cnt=0;
Segment s,e;
s.a=cen;s.b.y=cen.y;s.b.x=20000.0;
for(int i=0;i<n;i++){
e.a=p[i];e.b=p[i+1];
if(online(p[i],p[i+1],cen)) return false;
if(zero(p[i].y-p[i+1].y)) continue;
if(online(s.a,s.b,p[i])){
if(p[i].y>p[i+1].y) cnt++;
}
else if(online(s.a,s.b,p[i+1])){
if(p[i+1].y>p[i].y) cnt++;
}
else if(across(s,e))
cnt++;
}
return cnt&1;
}
inline void Get_Min_Dist(Point &cur){
double ret=inf;
for(int i=0;i<n;i++)
ret=min(ret,Dist_Point_Seg(cur,p[i],p[i+1]));
cur.val=ret;
}
int main(){
double r,best[105];
srand(time(NULL));
while(scanf("%d",&n)!=EOF&&n){
double maxx=0,maxy=0,minx=inf,miny=inf;
for(int i=0;i<n;i++){
scanf("%lf%lf",&p[i].x,&p[i].y);
maxx = maxx>p[i].x?maxx:p[i].x;
maxy = maxy>p[i].y?maxy:p[i].y;
minx = minx<p[i].x?minx:p[i].x;
miny = miny<p[i].y?miny:p[i].y;
}
p[n]=p[0];
scanf("%lf",&r);
int m=min(n,N);
for(int i=0;i<m;i++){
tp[i].x=(p[i].x+p[i+1].x)/2;
tp[i].y=(p[i].y+p[i+1].y)/2;
tp[i].val=0;
}
double step=sqrt((maxx-minx)*(maxx-minx)+(maxy-miny)*(maxy-miny))/2;
bool flag=false;
while(step>1e-3&&!flag){
for(int i=0;i<m&&!flag;i++){
for(int j=0;j<5&&!flag;j++){
double angle=rand();
cur.x=tp[i].x+step*cos(angle);
cur.y=tp[i].y+step*sin(angle);
if(!In_Polygon(cur)) continue;
Get_Min_Dist(cur);
if(cur.val+1e-3>tp[i].val){
tp[i]=cur;
if(cur.val+1e-3>r) flag=true;
}
}
}
step*=0.55;
}
puts(flag?"Yes":"No");
}
return 0;
}
