[ZOJ3338 Map]爬山法

【题目大意】
给出两个矩形，让你求一个点，使之满足在两个矩形里的比例位置是一样的。
【算法分析】
Orz。。。比赛时想爬山。但是弄成直接爬那个重合点，然后以他们比例差作为估价函数。
于是果断写不出，然后挂了。
然后赛后问师傅。。。师傅说直接爬外面的，再算在里面的对应位置就可以了。
当时当场Orz自己的傻×无限次。

然后其中一种正确的做法是：
在外面爬，然后算在里面的对应位置，估价函数就设为这两个对应点的距离。

于是一爬就过。。。Orz。。。
【CODE】
#include #include #include #include #include using namespace std;
const double eps=1e-5;
struct Point{double x,y;}a[5],st,xXL,yXL;
double ratex,ratey;

inline double sqr(double x){return x*x;}
inline double dis(Point A,Point B){return sqrt(sqr(A.x-B.x)+sqr(A.y-B.y));}

void input(){
scanf("%lf%lf",&st.x,&st.y);
for (int i=1;i<=4;i++)
scanf("%lf%lf",&a[i].x,&a[i].y);
ratex=dis(a[1],a[2])/st.x;
ratey=dis(a[1],a[4])/st.y;

xXL.x=a[2].x-a[1].x;
xXL.y=a[2].y-a[1].y;

yXL.x=a[4].x-a[1].x;
yXL.y=a[4].y-a[1].y;
}

double w(double x,double y){
if (x<0 || x>st.x || y<0 || y>st.y) return 1e50;
double rx=x/st.x,ry=y/st.y;
Point m,tmp;
tmp.x=x; tmp.y=y;

m.x=rx*xXL.x+ry*yXL.x+a[1].x;
m.y=rx*xXL.y+ry*yXL.y+a[1].y;
return dis(m,tmp);
}

void work(){
double step=1.0,x=0,y=0;
bool flag;
for (;step>eps;step/=2){
for (flag=true;flag;){
flag=false;
if (w(x+step,y) if (w(x-step,y) if (w(x,y+step) if (w(x,y-step) }
}
printf("%.2lf %.2lfn",x,y);
}

int main(){
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
input();
work();
}
}