【POJ】2165.Gunman

题解

把直线的斜率分解成二维，也就是随着z的增加x的增量和y的增量

我们发现一条合法直线向上移一点一定能碰到一条横线

知道了这条横线可以算出y的斜率

我们旋转一下，让这条横线碰到两条竖线，就可以算出x的斜率，进而判断直线在不在平面内

代码

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

//#define ivorysi

#define MAXN 105

#define eps 1e-8

using namespace std;

typedef long long int64;

typedef double db;

struct plane{

    double x[2],y[2],z;

}pl[MAXN];

struct Point{

    double x,y;

}P[MAXN * 4];

int N,cnt;

db yk,xk,sx;

void Init() {

    scanf("%d",&N);

    for(int i = 1 ; i <= N ; ++i) {

	scanf("%lf%lf%lf%lf%lf",&pl[i].x[0],&pl[i].y[0],&pl[i].x[1],&pl[i].y[1],&pl[i].z);

    }

}

void Solve() {

    for(int i = 1 ; i <= N ; ++i) {

	for(int r = 0 ; r <= 1 ; ++r) {

	    db k = pl[i].y[r] / pl[i].z;

	    cnt = 0;

	    bool flag = 0;

	    for(int j = 1 ; j <= N ; ++j) {

		if(pl[j].z * k > pl[j].y[1] + eps || pl[j].z * k < pl[j].y[0] - eps) goto succ;

		for(int c = 0 ; c <= 1 ; ++c) {

		    P[++cnt] = (Point){pl[j].x[c],pl[j].z};

		}

	    }

	    yk = k;

	    for(int j = 1 ; j <= cnt ; ++j) {

		for(int h = j + 1 ; h <= cnt ; ++h) {

		    if(P[j].y == P[h].y) continue;

		    flag = 1;

		    k = (P[j].x - P[h].x) / (P[j].y - P[h].y);

		    if(P[j].x == P[h].x) k = 0;

		    sx = P[j].x - P[j].y * k;

		    for(int l = 1 ; l <= N ; ++l) {

			db tmp = sx + k * pl[l].z;

			if(tmp < pl[l].x[0] - eps || tmp > pl[l].x[1] + eps) {flag = 0;break;}

		    }

		    if(flag) {

			xk = k;goto succ;

		    }

		}

	    }

	    succ:;

	    if(flag) {

		puts("SOLUTION");

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

		for(int i = 1 ; i <= N ; ++i) {

		    printf("%.6f %.6f %.6f\n",sx + xk * pl[i].z,yk * pl[i].z,pl[i].z);

		}

		return;

	    }

	}

    }

    puts("UNSOLVABLE");

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Init();

    Solve();

}