外卖小哥
缘起
大家知道 外卖小哥都是很辛苦的. 所以他们巴不得从接单处到用户住处能以最短路到达. 你能帮帮他们吗?
Uva 248 Cutting Corners
分析
平面上有一些矩形建筑物,一个人骑车从起点到终点，不能穿越任何建筑物，但可以沿着建筑物的边界骑车
输入保证起点和终点不会在建筑物内部. 并且确保从起点出发一定可以到达终点.
输入
多样例. 每个样例的第一行是 n, 表示建筑物的个数,0<= n <=20
第二行是四个浮点数 x1 y1 x2 y2 其中 (x1, y1) 是起点, (x2, y2) 是终点
然后是 n 行, 每行 6 个浮点数 x1 y1 x2 y2 x3 y3 表示矩形的3个顶点坐标.
坐标数据都在 [0, 1000] 内. 输入处理到 n = -1
输出
按照下方示例输出起点到终点的最短路径. 精确到小数点后2位. 两个样例输出之间用空行隔开.
样例输入
5
6.5 9 10 3
1 5 3 3 6 6
5.25 2 8 2 8 3.5
6 10 6 12 9 12
7 6 11 6 11 8
10 7 11 7 11 11
-1
样例输出
Scenario #1
route distance: 7.28
限制
3s
来源
ACM/ICPC 1996 World Finals
本题 n 比较小，所以考虑暴力枚举. 就是 通过计算几何 建图，最后跑最短路，
因为矩形给出了三个点，所以第四个点的坐标应该是唯一确定的. 而且确定方法很简单. 只需要先确定出给出的3个点中哪两个是对角线的两个点. 因为你三个点一定有一个是直角上的点. 所以枚举并用内积验证这个点. 一旦对角线上的两个点确定了，则
通过 ? + B = A + C 就知道 ? 是多少了.
所以本题建图是关键，首先按照上述方法对每个矩形先处理出第四个点，将矩形的四个点按照逆时针或顺时针存储. 然后 n个矩形 4n 个点, 然后顺次考察这些点. 对于严格在其他矩形内部的点，例如下图1中的 A，显然，这样的点是不会参与建图的. 所以要排除掉这种点. 而如何判断一个点严格在别的矩形内部呢? 一般的讲，这就是判定一个点和凸多边形的关系, 我们是有
一般算法的. 但其实我们有更简单的做法
P 严格在 矩形 ABCD 内部的充要条件是
或者
如果不排除这种严格在别的矩形内部的点的话，则例如上图要求从 B 到E 的最短路，则跑最短路会找到 B-->A-->E 这样的路线，但实际答案是 B-->C-->E. 这样就wa掉了.
得到点了之后（例如上图得到的点就应该是 B、C、D、E、F、G、H），再加上起点和终点. 然后就要开始考虑在这些点之间连边. 显然，连的边不能和任何矩形规范相交. 例如下图
AB 连边和矩形 CDEF 规范相交（表示会穿越建筑物），所以此边不能连. GH 没有和任何矩形规范相交，故可以连. IH 和 矩形AJGI 、矩形 BHKL 都规范相交, 所以IH 是不能连边的. 但是，这种考虑是有缺陷的. 例如下图三种情况
那 AB 连边到底要不要加呢? 如果要硬撸分析的话，会身陷漩涡不能自拔.
有一种极为巧妙的做法 or22222222222222222222222，就是给每个矩形人为的加上两条对角线. 变成
也就是说，我们判断一条边能不能连的标准依旧是不能和所有矩形的边有规范相交的情况. 但是矩形的边我们由四条周边多加了两条对角线. 于是问题就巧妙而优美的迎刃而解了.
//#include "stdafx.h"
//#define LOCAL
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#pragma warning(disable:4996)
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <iomanip>
#include <string>
#include <ctype.h>
#include <string.h>
#include <fstream>
#include <sstream>
#include <math.h>
#include <map>
//#include <unordered_map>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <time.h>
#include <stdlib.h>
#include <bitset>
using namespace std;
//#define int unsigned long long
//#define int long long
#define re register int
#define ci const int
#define ui unsigned int
typedef pair<int, int> P;
#define FE(cur) for(re h = head[cur], to; ~h; h = g[h].nxt)
#define ilv inline void
#define ili inline int
#define ilc inline char
#define ild inline double
#define ilp inline P
#define LEN(cur) (hjt[cur].r - hjt[cur].l)
#define MID(cur) (hjt[cur].l + hjt[cur].r >> 1)
#define SQUARE(x) ((x) * (x))
typedef vector<int>::iterator vit;
typedef set<int>::iterator sit;
typedef map<int, int>::iterator mit;
const int inf = ~0u>>1;
const double PI = acos(-1.0), eps = 1e-6;
namespace fastio
{
const int BUF = 1 << 21;
char fr[BUF], fw[BUF], *pr1 = fr, *pr2 = fr;int pw;
ilc gc() { return pr1 == pr2 && (pr2 = (pr1 = fr) + fread(fr, 1, BUF, stdin), *pr2 = 0, pr1 == pr2) ? EOF : *pr1++; }
ilv flush() { fwrite(fw, 1, pw, stdout); pw = 0; }
ilv pc(char c) { if (pw >= BUF) flush(); fw[pw++] = c; }
ili read(int &x)
{
x = 0; int f = 1; char c = gc(); if (!~c) return EOF;
while(!isdigit(c)) { if (c == '-') f = -1; c = gc(); }
while(isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = gc();
x *= f; return 1;
}
ili read(double &x)
{
int xx = 0; double f = 1.0, fraction = 1.0; char c = gc(); if (!~c) return EOF;
while (!isdigit(c)) { if (c == '-') f = -1.0; c = gc(); }
while (isdigit(c)) { xx = (xx << 3) + (xx << 1) + (c ^ 48), c = gc(); }
x = xx;
if (c ^ '.') { x = f * xx; return 1; }
c = gc();
while (isdigit(c)) x += (c ^ 48) * (fraction /= 10), c = gc();
x *= f; return 1;
}
ilv write(int x) { if (x < 0) pc('-'), x = -x; if (x > 9) write(x / 10); pc(x % 10 + 48); }
ilv writeln(int x) { write(x);pc(10); }
ili read(char *x)
{
char c = gc(); if (!~c) return EOF;
while(!isalpha(c) && !isdigit(c)) c = gc();
while (isalpha(c) || isdigit(c)) *x++ = c, c = gc();
*x = 0; return 1;
}
ili readln(char *x)
{
char c = gc(); if (!~c) return EOF;
while(c == 10) c = gc();
while(c >= 32 && c <= 126) *x++ = c, c = gc();
*x = 0; return 1;
}
ilv write(char *x) { while(*x) pc(*x++); }
ilv write(const char *x) { while(*x) pc(*x++); }
ilv writeln(char *x) { write(x); pc(10); }
ilv writeln(const char *x) { write(x); pc(10); }
ilv write(char c) { pc(c); }
ilv writeln(char c) { write(c); pc(10); }
} using namespace fastio;
#define cp const Point
const int maxn = 1005;
int n, g[85][85], v[maxn], inq[maxn];
double d[maxn][maxn], dis[maxn];
struct Point
{
double x, y;
Point(double x = 0, double y = 0):x(x), y(y){}
Point operator + (cp &o) const
{
return Point(x + o.x, y + o.y);
}
Point operator - (cp &o) const
{
return Point(x - o.x, y - o.y);
}
double operator / (cp &o) const
{
return x * o.y - y * o.x;
}
double operator * (cp &o) const
{
return x * o.x + y * o.y;
}
} ps[maxn], src, dst;
Point forth(cp &p1, cp &p2, cp &p3)
{
return p1 + p3 - p2;
}
ili dcmp(double x)
{
if (fabs(x) < eps) return 0;
return x < 0 ? -1 : 1;
}
ilv initp2(int i, cp &p1, cp &p2, cp &p3, cp &p4)
{
ps[4 * i] = p1;
ps[4 * i + 1] = p2;
ps[4 * i + 2] = p3;
ps[4 * i + 3] = p4;
}
ilv initp1(int i, cp &p1, cp &p2, cp &p3)
{
initp2(i, p1, p2, p3, forth(p1, p2, p3));
}
ilv initp(int i, cp &p1, cp &p2, cp &p3)
{
if (!dcmp((p2 - p1) * (p3 - p1))) initp1(i, p2, p1, p3);
if (!dcmp((p1 - p2) * (p3 - p2))) initp1(i, p1, p2, p3);
if (!dcmp((p1 - p3) * (p2 - p3))) initp1(i, p1, p3, p2);
}
ild direction(cp &p1, cp &p2, cp &p3)
{
return (p2 - p1) / (p3 - p1);
}
ili ck1(cp &p, cp &p1, cp &p2, cp &p3, cp &p4)
{
int t = dcmp(direction(p, p1, p2)) + dcmp(direction(p, p2, p3)) + dcmp(direction(p, p3, p4)) + dcmp(direction(p, p4, p1));
return t == 4 || t == -4;
}
ili ck(int i)
{
for (re j = 0; j < 4 * n; j++)
{
if (i / 4 == j / 4)
{
continue;
}
if (ck1(ps[i], ps[j / 4 * 4], ps[j / 4 * 4 + 1], ps[j / 4 * 4 + 2], ps[j / 4 * 4 + 3]))
{
return 0;
}
}
return 1;
}
ili intersect(cp &p1, cp &p2, cp &p3, cp &p4)
{
double d1 = direction(p1, p2, p3);
double d2 = direction(p1, p2, p4);
double d3 = direction(p3, p4, p1);
double d4 = direction(p3, p4, p2);
return dcmp(d1 * d2) + dcmp(d3 * d4) == -2;
}
ili ck3(cp &a, cp &b, cp &p1, cp &p2, cp &p3, cp &p4)
{
if (intersect(a, b, p1, p2)) return 1;
if (intersect(a, b, p2, p3)) return 1;
if (intersect(a, b, p3, p4)) return 1;
if (intersect(a, b, p4, p1)) return 1;
if (intersect(a, b, p1, p3)) return 1;
if (intersect(a, b, p2, p4)) return 1;
return 0;
}
ili ck2(int i, int j)
{
for (re k = 0; k < 4 * n; k += 4)
{
if (ck3(ps[i], ps[j], ps[k], ps[k + 1], ps[k + 2], ps[k + 3]))
{
return 0;
}
}
return 1;
}
ild getd(cp &p1, cp &p2)
{
return sqrt(SQUARE(p1.x - p2.x) + SQUARE(p1.y - p2.y));
}
ild spfa()
{
memset(inq, 0, sizeof(inq));
fill(dis, dis + 4 * n + 3, inf);
dis[4 * n] = 0;
queue<int> q;
q.push(4 * n);
inq[4 * n] = 1;
while (!q.empty())
{
int front = q.front(); q.pop();
inq[front] = 0;
for (re i = 0; i < 4 * n + 2; i++)
{
if (g[front][i] && dis[i] > dis[front] + d[front][i])
{
dis[i] = dis[front] + d[front][i];
if (!inq[i])
{
inq[i] = 1;
q.push(i);
}
}
}
}
return dis[4 * n + 1];
}
double kk()
{
for (re i = 0; i < 4 * n; i++) // 蒯点
{
if (ck(i))
{
v[i] = 1;
}
}
v[4 * n] = v[4 * n + 1] = 1;
for (re i = 0; i < 4 * n + 1; i++) // 建弧
{
for (re j = i + 1; j < 4 * n + 2; j++)
{
if (v[i] && v[j] && ck2(i, j))
{
g[i][j] = g[j][i] = 1;
d[i][j] = d[j][i] = getd(ps[i], ps[j]);
}
}
}
return spfa();
}
signed main()
{
#ifdef LOCAL
FILE *ALLIN = freopen("d:\\data.in", "r", stdin);
// freopen("d:\\my.out", "w", stdout);
#endif
int kase = 0;
while (read(n), ~n)
{
read(src.x), read(src.y); read(dst.x), read(dst.y);
double x1, y1, x2, y2, x3, y3;
for (re i = 0; i < n; i++)
{
read(x1), read(y1), read(x2), read(y2), read(x3), read(y3);
initp(i, Point(x1, y1), Point(x2, y2), Point(x3, y3));
}
ps[4 * n] = src; ps[4 * n + 1] = dst;
memset(g, 0, sizeof(g)); memset(v, 0, sizeof(v));
if (kase++)
{
puts("");
}
printf("Scenario #%d\n route distance: %.2lf\n",kase ,kk());
}
flush();
#ifdef LOCAL
fclose(ALLIN);
#endif
return 0;
}
ac情况
Accepted 30ms C++11 5.3.0
温馨提示
如果你喜欢本文，请分享到朋友圈，想要获得更多信息，请关注ACM算法日常。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-07-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录