首页 > ACM题库 > HDU-杭电 > HDU 4617-Weapon-计算几何-[解题报告]HOJ
2015
09-17

HDU 4617-Weapon-计算几何-[解题报告]HOJ

Weapon

问题描述 :

  Doctor D. are researching for a horrific weapon. The muzzle of the weapon is a circle. When it fires, rays form a cylinder that runs through the circle verticality in both side. If one cylinder of rays touch another, there will be an horrific explosion. Originally, all circles can rotate easily. But for some unknown reasons they can not rotate any more. If these weapon can also make an explosion, then Doctor D. is lucky that he can also test the power of the weapon. If not, he would try to make an explosion by other means. One way is to find a medium to connect two cylinder. But he need to know the minimum length of medium he will prepare. When the medium connect the surface of the two cylinder, it may make an explosion.

输入:

  The first line contains an integer T, indicating the number of testcases. For each testcase, the first line contains one integer N(1 < N < 30), the number of weapons. Each of the next 3N lines&nbsp; contains three float numbers. Every 3 lines represent one weapon. The first line represents the coordinates of center of the circle, and the second line and the third line represent two points in the circle which surrounds the center. It is supposed that these three points are not in one straight line. All float numbers are between -1000000 to 1000000.

输出:

  The first line contains an integer T, indicating the number of testcases. For each testcase, the first line contains one integer N(1 < N < 30), the number of weapons. Each of the next 3N lines&nbsp; contains three float numbers. Every 3 lines represent one weapon. The first line represents the coordinates of center of the circle, and the second line and the third line represent two points in the circle which surrounds the center. It is supposed that these three points are not in one straight line. All float numbers are between -1000000 to 1000000.

样例输入:

3
3
0 0 0
1 0 0
0 0 1
5 2 2
5 3 2
5 2 3
10 22 -2
11 22 -1
11 22 -3
3
0 0 0
1 0 1.5
1 0 -1.5
112 115 109
114 112 110
109 114 111
-110 -121 -130
-115 -129 -140
-104 -114 -119.801961
3
0 0 0
1 0 1.5
1 0 -1.5
112 115 109
114 112 110
109 114 111
-110 -121 -130
-120 -137 -150
-98 -107 -109.603922

样例输出:

Lucky
2.32
Lucky

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4617


题意:给出空间内的n个圆的圆心及圆上两点,即n个无限延长的光柱的截面,问这些圆柱是否会交在一起,如果不交输出最短距离,否则输出"Lucky"


思路:对于每个圆,找出其法向量直线,这样每两条法向量直线的间距减去两圆的半径和即是距离,判断该距离是否<=0即可

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <utility>
#include <functional>
#include <vector>
#include <queue>
#include <string>
#include <set>
#include <map>
#pragma comment (linker, "/STACK:1024000000,1024000000")

#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define eps 1e-8
#define sign(x) ((x) > eps ? 1 : ((x) < -eps ? (-1) : (0)))

using namespace std;

typedef long long ll;

int n;

struct point
{
    double x, y, z;
    point() {}
    point(double _x, double _y, double _z)
    {
        x = _x;
        y = _y;
        z = _z;
    }
    void input()
    {
        scanf("%lf%lf%lf", &x, &y, &z);
    }
    point operator + (const point &b) const
    {
        return point(x + b.x, y + b.y, z + b.z);
    }
};

struct line
{
    point a, b;
};

struct circle
{
    point o, p1, p2;

    void input()
    {
        o.input();
        p1.input();
        p2.input();
    }
} c[100];

point xmult(point u, point v)
{
    point ret;
    ret.x = u.y * v.z - v.y * u.z;
    ret.y = u.z * v.x - u.x * v.z;
    ret.z = u.x * v.y - u.y * v.x;
    return ret;
}

double dis(point u, point v)
{
    return sqrt((u.x - v.x) * (u.x - v.x) + (u.y - v.y) * (u.y - v.y) + (u.z - v.z) * (u.z - v.z));
}

double dmult(point u, point v)
{
    return u.x * v.x + u.y * v.y + u.z * v.z;
}

point sub(point u, point v)
{
    point ret;
    ret.x = u.x - v.x;
    ret.y = u.y - v.y;
    ret.z = u.z - v.z;
    return ret;
}

double vlen(point p)
{
    return sqrt(p.x * p.x + p.y * p.y + p.z * p.z);
}

point pvec(circle s)
{
    return xmult(sub(s.o, s.p1), sub(s.p1, s.p2));
}

double linedis(line u, line v)
{
    point n = xmult(sub(u.a, u.b), sub(v.a, v.b));
    return fabs(dmult(sub(u.a, v.a), n)) / vlen(n);
}

void solve()
{
    double ans = 1e9;
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
        {
            circle c1 = c[i], c2 = c[j];
            double r1 = dis(c[i].o, c[i].p1);
            double r2 = dis(c[j].o, c[j].p1);

            point k1 = pvec(c1);
            point k2 = pvec(c2);

            line l1, l2;
            l1.a = c1.o, l1.b = k1 + c1.o;
            l2.a = c2.o, l2.b = k2 + c2.o;

            double d = linedis(l1, l2);
            if(sign(d - r1 - r2) <= 0)
            {
                puts("Lucky");
                return ;
            }
            ans = min(ans, d - r1 - r2);
        }
    }
    printf("%.2f\n", ans);
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
            c[i].input();
        solve();
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/fipped/article/details/45028825