首页 > 代码库 > HDU 3272 - Mission Impossible（计算几何）

HDU 3272 - Mission Impossible（计算几何）

2024-07-17 22:23:02   220人阅读

HDU 3272 - Mission Impossible（计算几何）

ACM

题目地址： 
HDU 3272 - Mission Impossible

题意： 
在二维平面上，给你一个初始位置(hx,hy)，你需要获得四种资源，A在x轴上任意位置，B在y轴上任意位置，C、D位置会告诉你。问获得四种资源后返回(hx,hy)最短要走多长。

分析： 
三条线段与X、Y轴相交有三种情况：

  1. 与x,y都相交，此时最短距离为周长
  2. 仅与X或Y相交，这时枚举每条边，利用镜像对称算出距离，取最小值
  3. 与X和Y都不相交，这个比较不好想 
    我曾天真的以为只要枚举每条边，让它拐到中点就行... 
    可以分两种情况 
    第一种： 
     
    第二种： 
     
    第一种情况要枚举六次， 一条边负责去X轴另一个条负责取Y轴。 
    第二种情况要枚举三次，每条边的两上端点同时取X轴和Y轴。

代码：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        3272.cpp
*  Create Date: 2014-08-15 20:56:16
*  Descripton:   
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define repf(i,a,b) for(int i=(a);i<=(b);i++)

typedef long long ll;

const int N = 0;

struct Point {
	double x;
	double y;
} h, o, p[3];

double dis(const Point& a, const Point& b) {
	return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

// calc h->a->b->h
double calc(int a, int b) {
	double ret = dis(h, p[a]) + dis(p[a], p[b]) + dis(p[b], h);
	double ha, ab, bh;
	bool cx = 0, cy = 0;
	if (h.x * p[a].x <= 0 || p[a].x * p[b].x <= 0 || p[b].x * h.x <= 0)
		cx = 1;
	if (h.y * p[a].y <= 0 || p[a].y * p[b].y <= 0 || p[b].y * h.y <= 0)
		cy = 1;

	if (cx == 0 && cy == 0) {
		// 3
		Point t1, t2;
		t1.x = h.x;
		t1.y = -h.y;
		t2.x = -p[a].x;
		t2.y = p[a].y;
		ha = ret - dis(h, p[a]) + dis(t1, t2);
		t1.x = p[b].x;
		t1.y = -p[b].y;
		t2.x = -p[a].x;
		t2.y = p[a].y;
		ab = ret - dis(p[a], p[b]) + dis(t1, t2);
		t1.x = p[b].x;
		t1.y = -p[b].y;
		t2.x = -h.x;
		t2.y = h.y;
		bh = ret - dis(h, p[b]) + dis(t1, t2);
		double ans = min(ha, min(ab, bh));

		// 6
		// ha->x ab->y
		t1.x = p[a].x;
		t1.y = -p[a].y;
		t2.x = -p[a].x;
		t2.y = p[a].y;
		ans = min(ans, ret - dis(p[a], h) + dis(t1, h) - dis(p[a], p[b]) + dis(t2, p[b]));
		
		// ha->x bh->y
		t1.x = h.x;
		t1.y = -h.y;
		t2.x = -h.x;
		t2.y = h.y;
		ans = min(ans, ret - dis(p[a], h) + dis(p[a], t1) - dis(h, p[b]) + dis(t2, p[b]));
		
		// ab->x ha->y
		t1.x = p[a].x;
		t1.y = -p[a].y;
		t2.x = -p[a].x;
		t2.y = p[a].y;
		ans = min(ans, ret - dis(p[a], p[b]) + dis(t1, p[b]) - dis(p[a], h) + dis(t2, h));
		
		// ab->x bh->y
		t1.x = p[b].x;
		t1.y = -p[b].y;
		t2.x = -p[b].x;
		t2.y = p[b].y;
		ans = min(ans, ret - dis(p[a], p[b]) + dis(t1, p[a]) - dis(p[b], h) + dis(t2, h));

		// bh->x ha->y
		t1.x = h.x;
		t1.y = -h.y;
		t2.x = -h.x;
		t2.y = h.y;
		ans = min(ans, ret - dis(p[b], h) + dis(p[b], t1) - dis(h, p[a]) + dis(t2, p[a]));
		
		// bh->x ab->y
		t1.x = p[b].x;
		t1.y = -p[b].y;
		t2.x = -p[b].x;
		t2.y = p[b].y;
		ans = min(ans, ret - dis(h, p[b]) + dis(t1, h) - dis(p[b], p[a]) + dis(t2, p[a]));

		ret = ans;
	} else if (cx == 1 && cy == 0) {
		Point tmp;
		// tmp is x axis mirror of a
		tmp.x = p[a].x;
		tmp.y = -p[a].y;
		ha = ret - dis(h, p[a]) + dis(h, tmp);
		ab = ret - dis(p[a], p[b]) + dis(tmp, p[b]);

		// tmp is x axis mirror of b
		tmp.x = p[b].x;
		tmp.y = -p[b].y;
		bh = ret - dis(h, p[b]) + dis(h, tmp);

		ret = min(ha, min(ab, bh));
	} else if (cx == 0 && cy == 1) {
		Point tmp;
		// tmp is y axis mirror of a
		tmp.x = -p[a].x;
		tmp.y = p[a].y;
		ha = ret - dis(h, p[a]) + dis(h, tmp);
		ab = ret - dis(p[a], p[b]) + dis(tmp, p[b]);

		// tmp is y axis mirror of b
		tmp.x = -p[b].x;
		tmp.y = p[b].y;
		bh = ret - dis(h, p[b]) + dis(h, tmp);

		ret = min(ha, min(ab, bh));
	}

	return ret;
}

int main() {
	// ori
	o.x = 0;
	o.y = 0;
	
	int t;
	cin >> t;
	while (cin >> p[0].x >> p[0].y >> p[1].x >> p[1].y >> h.x >> h.y) {
		printf("%.2f\n", calc(0, 1));
	}
	return 0;
}



联系
我们