HDU 3007
最小圆覆盖
#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-7
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
struct point{
double x,y;
} a[510];
int n;
double D(point a,point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dis(-1,1);
double ansx,ansy;
double solve(double X){
double step=1e3,x=0,y=0;
point p;
double ans=X;
while(step>1e-8){
p.x=x+dis(rng)*step;p.y=y+dis(rng)*step;
double tm=0;
for(int i=0; i<n;i++) tm=max(tm,D(p,a[i]));
if (tm<ans){
ans=tm;
ansx=x=p.x,ansy=y=p.y;
}else
if (exp((tm-ans)/step)<(dis(rng)+1)/2) x=p.x,y=p.y;
step*=0.98;
}
return ans;
}
int main()
{
while(~scanf("%d",&n))
{
if (!n) break;
for(int i=0; i<n; i++)scanf("%lf%lf",&a[i].x,&a[i].y);
double ans=1e3;
ans=min(ans,solve(ans));
printf("%.2f %.2f %.2f\n",ansx,ansy,ans);
}
return 0;
}
HDU 3644
多边形内能否嵌套一个给定半径的圆
其实就是看多边形里嵌套的最大圆的半径
牛逼的地方，在于多个点同时跑退火，起始是每条线段的中点，然后随机角度，在该角度增加 step，还有个牛逼的地方，对于当前 step 不能只随机1次，因为可能随机到多边形外部，所以要多随机几次，最后牛逼的地方，降温系数不是通常的 0.98、0.99 只需要 0.8 左右，没错只要 0.8！！！
模拟退火水好深
#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 998244353
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
inline int dcmp(double x){if (x<=-eps) return -1;else return x>=eps?1:0;}
struct Point{
double x,y;
Point(double x=0,double y=0):x(x),y(y){ }
}a[60],c[60];
double d[60];
typedef Point Vector;
Vector operator + (Vector a,Vector b){return Vector(a.x+b.x,a.y+b.y);}
Vector operator - (Vector a,Vector b){return Vector(a.x-b.x,a.y-b.y);}
Vector operator * (Vector a,double b){return Vector(a.x*b,a.y*b);}
Vector operator / (Vector a,double b){return Vector(a.x/b,a.y/b);}
bool operator == (Vector a,Vector b){return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;}
double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;} //点积
double Length(Vector a){return sqrt(Dot(a,a));}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;} //叉积
//点到线段的距离,p到线段ab的距离，若距离不存在，返回pa，pb中较短的线段的距离
double DistanceToSegment(Point p,Point a,Point b)
{
if (a==b)return Length(p-a);
Vector v1=b-a,v2=p-a,v3=p-b;
if (dcmp(Dot(v1,v2))<0)return Length(v2);
else if (dcmp(Dot(v1,v3))>0)return Length(v3);
else return fabs(Cross(v1,v2))/Length(v1);
}
//点在线段上（包含端点），在为 1 ，不在为 0
bool isPointOnSegment(Point P,Point A,Point B){
return dcmp(Cross(A-P,B-P))==0 && dcmp(Dot(A-P,B-P))<=0; // 不包含端点时为 <0
}
//点在多边形内判定
int isPointInPolygon(Point p,Point* poly,int n)
{
int wn=0;
for(int i=0;i<n;i++){
if(isPointOnSegment(p,poly[i],poly[(i+1)%n])) return -1;//在边界上
int k=dcmp(Cross(poly[(i+1)%n]-poly[i], p-poly[i]));
int d1=dcmp(poly[i].y-p.y);
int d2=dcmp(poly[(i+1)%n].y-p.y);
if(k>0 && d1<=0 && d2>0) wn++;
if(k<0 && d2<=0 && d1>0) wn--;
}
if(wn!=0) return 1; //在内部
return 0; //在外部
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double solve(int n){
double step=1e3;
Point p;
while(step>1e-5){
for(int i=0;i<n;i++)
for(int j=0;j<5;j++){
double ang=rng();
p.x=c[i].x+step*cos(ang);p.y=c[i].y+step*sin(ang);
if(isPointInPolygon(p,a,n)==1){
double tm=1e3;
for(int i=0;i<n;i++) tm=min(tm,DistanceToSegment(p,a[i],a[i+1]));
if (tm>d[i])c[i]=p,d[i]=tm;
}
}
step*=0.75;
}
return *max_element(d,d+n);
}
int main()
{
int n; double r;
while(~scanf("%d",&n))
{
if (!n) break;
for(int i=0; i<n; i++)scanf("%lf%lf",&a[i].x,&a[i].y);
scanf("%lf",&r);
a[n]=a[0];
for(int i=0;i<n;i++) c[i]=(a[i]+a[i+1])/2,d[i]=0;
double ans=solve(n);
if(dcmp(ans-r)>=0) puts("Yes");else puts("No");
}
return 0;
}
HDU 5017
椭球面上找距离原点最近的点
更新 x,y，解二元一次方程算出 z ,更新最优值即可
#include<bits/stdc++.h>
#define N 1000010
#define INF 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 998244353
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
inline int dcmp(double x){if (x<=-eps) return -1;else return x>=eps?1:0;}
double a,b,c,d,e,f;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double slove(){
double x=sqrt(1/a),y=0,z;double ans=x;
double step=2,tx,ty;
while(step>1e-9){
for(int i=0;i<5;i++){
double ang=rng();
tx=x+step*cos(ang),ty=y+step*sin(ang);
double A=c,B=d*ty+e*tx,C=a*tx*tx+b*ty*ty+f*tx*ty-1;
double delta=B*B-4.0*A*C,tm;
if (delta<0) continue;
z=(-B-sqrt(delta))/A/2;
tm=sqrt(z*z+tx*tx+ty*ty);
if (tm<ans) ans=tm,x=tx,y=ty;
z=(-B+sqrt(delta))/A/2;
tm=sqrt(z*z+tx*tx+ty*ty);
if (tm<ans) ans=tm,x=tx,y=ty;
}
step*=0.98;
}
return ans;
}
int main()
{
while(~scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)){
double ans=10;
for(int i=0;i<2;i++) ans=min(ans,slove());
printf("%.6f\n",ans);
}
return 0;
}
HDU 2899
求一个函数最小值
#include<bits/stdc++.h>
#define N 50010
#define INF 0x3f3f3f3f
#define eps 1e-7
#define pi 3.141592653589793
#define mod 998244353
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dis(-1.0,1.0);
double y;
inline double f(double x){
return pow(x,7)*6+pow(x,6)*8+pow(x,3)*7+pow(x,2)*5-y*x;
}
double slove(){
double step=50,x=50,ans=f(x);
while(step>1e-15){
for(int i=0;i<5;i++){
double tmp=x+step*dis(rng);
if (tmp<0||tmp>100) continue;
double tt=f(tmp);
if (tt<ans)
ans=tt,x=tmp;
}
step*=0.99;
}
return ans;
}
int main(int argc, char const *argv[])
{
int T;sc(T);
while(T--){
scanf("%lf",&y);
printf("%.4f\n",slove());
}
return 0;
}
HDU 3932
#include<bits/stdc++.h>
#define N 50010
#define INF 0x3f3f3f3f
#define eps 1e-7
#define pi 3.141592653589793
#define mod 998244353
// #define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
uniform_real_distribution<double> dis(-1.0,1.0);
double X,Y,x[N],y[N],ax,ay; int n;
int dx[]={0,1,1,1,0,-1,-1,-1};
int dy[]={1,1,0,-1,-1,-1,0,1};
double f(double p,double q){
double res=0;
for(int i=0;i<n;i++){
double t=sqrt((p-x[i])*(p-x[i])+(q-y[i])*(q-y[i]));
res=max(res,t);
} return res;
}
double slove(){
double step=10000; ax=0,ay=0;double ans=f(ax,ay);
while(step>1e-15){
for(int i=0;i<16;i++){
double k=rng();
double tx=ax+step*cos(k),ty=ay+step*sin(k);
if (tx<0||tx>X||ty<0||ty>Y) continue;
double tt=f(tx,ty);
if (tt<ans)
ans=tt,ax=tx,ay=ty;
}
step*=0.95;
}
return ans;
}
int main(int argc, char const *argv[])
{
while(~scanf("%lf%lf%d",&X,&Y,&n)){
for(int i=0;i<n;i++) scanf("%lf%lf",&x[i],&y[i]);
double ans=slove();
printf("(%.1f,%.1f).\n%.1f\n",ax,ay,ans);
}
return 0;
}
京公网安备 11010502036488号