[POJ 2165] | Eurce's Blog

计算几何。

题意是，在一个三维直角坐标系上，有平行于xOy平面的n个矩形，其边与x、y轴平行，坐标取值范围(0,1000)。问在x轴上是否存在一点能引出一条直线与所有矩形都相交。

这题读完后，并没有太直观的思路。但由于数据规模不大，考虑用三分法。每次对枚举的double m，按z值的增序遍历所有矩形，维护一个窗口作为能与所有矩形都相交的区域，最后返回相交矩形的数目。基本的想法是，由于矩形是连续且规则的图形，那么若解存在，则必定有最大值为n的单峰存在。但WA了数次后发现，由于返回值是离散的，就无法通过严格单调性来对三分法上下界进行修改了。

随后又发现，m值的所有可能取值其实是有限的，为某两个矩形i和j间(xi,0,zi)与(xj,0,zj)所确定的直线与x轴的交点，这里xi或xj可以是矩形的左或右边界。因此枚举的m值总数是O(n^2)的。而用前面描述的遍历方法便能确定从该点出发是否与所有矩形相交。所以总复杂度是O(n^3)的。在n=100的情况下，是可以AC的。最后跑了235ms。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

#define eps 1e-8

int n;
double x1[100],y1[100],x2[100],y2[100],z[100];

void init()
{
    int i;
    for(i=0;i<n;i++)
        scanf("%lf%lf%lf%lf%lf",x1+i,y1+i,x2+i,y2+i,z+i);
}

int calc(double m)
{
    int i,d;
    double xl,yb,xr,yt;
    for(xl=x1[0],yb=y1[0],xr=x2[0],yt=y2[0],i=1,d=1;i<n;i++)
    {
        xl=m+(xl-m)/z[i-1]*z[i]; yb=yb/z[i-1]*z[i];
        xr=m+(xr-m)/z[i-1]*z[i]; yt=yt/z[i-1]*z[i];
        xl=min(xr,max(xl,x1[i]));
        yb=min(yt,max(yb,y1[i]));
        xr=max(xl,min(xr,x2[i]));
        yt=max(yb,min(yt,y2[i]));
        if(xl>x1[i]-eps&&xl<x2[i]+eps
                &&yb>y1[i]-eps&&yb<y2[i]+eps)
            d++;
    }
    return d;
}

void mksol(double m)
{
    int i;
    double xl,yb,xr,yt;
    puts("SOLUTION");
    printf("%.6f\n",m);
    for(xl=x1[0],yb=y1[0],xr=x2[0],yt=y2[0],i=1;i<n;i++)
    {
        xl=m+(xl-m)/z[i-1]*z[i]; yb=yb/z[i-1]*z[i];
        xr=m+(xr-m)/z[i-1]*z[i]; yt=yt/z[i-1]*z[i];
        xl=min(xr,max(xl,x1[i]));
        yb=min(yt,max(yb,y1[i]));
        xr=max(xl,min(xr,x2[i]));
        yt=max(yb,min(yt,y2[i]));
    }
    for(i=0;i<n;i++)
        printf("%.6f %.6f %.6f\n",m+(xl-m)/z[n-1]*z[i],
                yb/z[n-1]*z[i],z[i]);
}

void solve()
{
    int i,j;
    double m;
    for(i=0;i<n-1;i++)
    {
        for(j=i+1;j<n;j++)
        {
            m=x1[i]-z[i]*(x1[i]-x2[j])/(z[i]-z[j]);
            if(calc(m)==n)
                break;
            m=x1[i]-z[i]*(x1[i]-x1[j])/(z[i]-z[j]);
            if(calc(m)==n)
                break;
            m=x2[i]-z[i]*(x2[i]-x1[j])/(z[i]-z[j]);
            if(calc(m)==n)
                break;
            m=x2[i]-z[i]*(x2[i]-x2[j])/(z[i]-z[j]);
            if(calc(m)==n)
                break;
        }
        if(j<n)
            break;
    }
    if(i==n-1)
        puts("UNSOLVABLE");
    else
        mksol(m);
}

int main()
{
    while(~scanf("%d",&n))
    {
        init();
        solve();
    }
    return 0;
}

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define eps 1e-8

int n;

double x1[100],y1[100],x2[100],y2[100],z[100];

void init()

{

int i;

for(i=0;i<n;i++)

scanf("%lf%lf%lf%lf%lf",x1+i,y1+i,x2+i,y2+i,z+i);

}

int calc(double m)

{

int i,d;

double xl,yb,xr,yt;

for(xl=x1[0],yb=y1[0],xr=x2[0],yt=y2[0],i=1,d=1;i<n;i++)

{

xl=m+(xl-m)/z[i-1]*z[i]; yb=yb/z[i-1]*z[i];

xr=m+(xr-m)/z[i-1]*z[i]; yt=yt/z[i-1]*z[i];

xl=min(xr,max(xl,x1[i]));

yb=min(yt,max(yb,y1[i]));

xr=max(xl,min(xr,x2[i]));

yt=max(yb,min(yt,y2[i]));

if(xl>x1[i]-eps&&xl<x2[i]+eps

&&yb>y1[i]-eps&&yb<y2[i]+eps)

d++;

}

return d;

}

void mksol(double m)

{

int i;

double xl,yb,xr,yt;

puts("SOLUTION");

printf("%.6f\n",m);

for(xl=x1[0],yb=y1[0],xr=x2[0],yt=y2[0],i=1;i<n;i++)

{

xl=m+(xl-m)/z[i-1]*z[i]; yb=yb/z[i-1]*z[i];

xr=m+(xr-m)/z[i-1]*z[i]; yt=yt/z[i-1]*z[i];

xl=min(xr,max(xl,x1[i]));

yb=min(yt,max(yb,y1[i]));

xr=max(xl,min(xr,x2[i]));

yt=max(yb,min(yt,y2[i]));

}

for(i=0;i<n;i++)

printf("%.6f %.6f %.6f\n",m+(xl-m)/z[n-1]*z[i],

yb/z[n-1]*z[i],z[i]);

}

void solve()

{

int i,j;

double m;

for(i=0;i<n-1;i++)

{

for(j=i+1;j<n;j++)

{

m=x1[i]-z[i]*(x1[i]-x2[j])/(z[i]-z[j]);

if(calc(m)==n)

break;

m=x1[i]-z[i]*(x1[i]-x1[j])/(z[i]-z[j]);

if(calc(m)==n)

break;

m=x2[i]-z[i]*(x2[i]-x1[j])/(z[i]-z[j]);

if(calc(m)==n)

break;

m=x2[i]-z[i]*(x2[i]-x2[j])/(z[i]-z[j]);

if(calc(m)==n)

break;

}

if(j<n)

break;

}

if(i==n-1)

puts("UNSOLVABLE");

else

mksol(m);

}

int main()

{

while(~scanf("%d",&n))

{

init();

solve();

}

return 0;

}