absi2011's Blog & Daily Life.

全新的开始       我要省选翻盘       I wanna AK in 高考\化学       自此,生无可恋
[破碎的状态] [-30] Hdu 3644
[破碎的状态] [-26] 100543 J

[破碎的状态] [-29] Codeforces 2C

absi2011 posted @ Jun 23, 2016 05:10:42 PM in 刷题记录 with tags 小高考 搜索 模拟退火 CF 瞎搞 , 430 阅读

题意:(感谢@JCarlson 翻译)

题意:

有三个圆

求一个点x,使得这个点到每个圆的切线夹角相等

如果多个点,应该找到那个让夹角尽可能大的点

我造了个几何画板..

拖动选中的点旋转,显然角度不变

进行伸缩,显然角度不变

我们可以得到结论:

如果某个点x到圆心的距离d 比上这个圆的半径r是个定值

那么角度不变

模拟退火这个点,我们设定这个点的位置到每个圆心的位置/r的最大差为目标值

求最小化这个目标值即可..

多退几次即可..(虽然我不知道为啥可能会有多个可行解)

卡精度设置的小一点..

(实际上写的时候我设置的是距离的平方*别的r,避免除法和sqrt..)

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define y1 dream
int x1,y1,r1;
int x2,y2,r2;
int x3,y3,r3;
double nowx,nowy;
double cur_ans;
inline double dist(double x1,double y1,double x2,double y2)
{
    return (x2-x1)*(x2-x1)+(y2-y1)*(y2-y1);
}
double ans1,ans2,ans3;
inline double calc_ans(double x,double y)
{
    ans1=dist(x1,y1,x,y)*r2*r2*r3*r3;
    ans2=dist(x2,y2,x,y)*r3*r3*r1*r1;
    ans3=dist(x3,y3,x,y)*r1*r1*r2*r2;
    return max(max(fabs(ans1-ans2),fabs(ans2-ans3)),fabs(ans1-ans3));
}
const double eps=1e-3;
bool try_find_ans()
{
    double t=0.9;
    double size=500;
    nowx=rand()%1000;
    nowy=rand()%1000;
    double cur_ans=calc_ans(nowx,nowy);
    for (;;)
    {
        double c=rand()/(double)RAND_MAX-0.5;
        double deltax=c*size;
        if (size<1e-11) return false;
        c=rand()/(double)RAND_MAX-0.5;
        double deltay=c*size;
        double newx=nowx+deltax;
        double newy=nowy+deltay;
        double new_ans=calc_ans(newx,newy);
        if (new_ans<cur_ans)
        {
            cur_ans=new_ans;
            nowx=newx;
            nowy=newy;
            if ((ans1-ans2<eps)&&(ans2-ans3<eps)&&(ans3-ans1<eps))
            {
                return true;
            }
        }
        else
        {
            if (exp(-(new_ans-cur_ans)/t)*RAND_MAX>rand())
            {
                cur_ans=new_ans;
                nowx=newx;
                nowy=newy;
            }
            t*=0.9;
        }
        size*=0.99;
    }
    return false;
}
double min_ans;
double min_nowx;
double min_nowy;
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    scanf("%d%d%d%d%d%d%d%d%d",&x1,&y1,&r1,&x2,&y2,&r2,&x3,&y3,&r3);
    int i;
    min_ans=1e100;
    for (i=0;i<100;i++)
    {
        if (try_find_ans())
        {
            if (ans1<min_ans)
            {
                min_ans=ans1;
                min_nowx=nowx;
                min_nowy=nowy;
            }
        }
    }
    if (min_ans>1e99) return 0;
    printf("%.5lf %.5lf\n",min_nowx,min_nowy);
    return 0;
}
Avatar_small
ジミ=カルソン 说:
Jun 24, 2016 05:47:59 PM

才注意你这题意的问题……啥叫这个点到每个点的切线夹角相等,明明是这个点到每个圆的切线夹角相等


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter