外卖小哥

缘起

大家知道 外卖小哥都是很辛苦的. 所以他们巴不得从接单处到用户住处能以最短路到达. 你能帮帮他们吗?

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,显然,这样的点是不会参与建图的. 所以要排除掉这种点. 而如何判断一个点严格在别的矩形内部呢? 一般的讲,这就是判定一个点和凸多边形的关系, 我们是有

O(\log n)

一般算法的. 但其实我们有更简单的做法

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算法日常

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:影法師の物語

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 位置和方向的世界,计算几何的基本问题

    本文从最基本的线段相交问题出发,从解析几何进入计算几何,介绍点积和叉积这个最基本的计算几何工具,引入计算几何这个关于位置和方向的大航海世界~

    ACM算法日常
  • n维空间的多面体的有向测度和重心

    在《三维凸包》中我们学习了如何求三维空间中的点集凸包,本文来论述二维、三维甚至高位几何体的测度和重心的计算. 所谓测度,对于二维,指的是面积,对于三维,指的是体...

    ACM算法日常
  • 莫比乌斯函数入门

    要解决这道题目,它要求莫比乌斯(Mobius)函数作为知识背景. 所以我们先来学习一下mobius函数.

    ACM算法日常
  • 数据结构——最小生成树(C++和Java实现)

    快要一整个月没有更新博客了,之前的几周每周都想着要写,但是最后时间还是排不开,最近的状态是一直在写代码,一直在怼工作的需求,顺便刷刷算法题,国庆则是没心没肺的玩...

    Originalee
  • 2019 HDU多校第五场 1002.three arrays(01字典树)

    用户2965768
  • 每日一题 C++版(汽水瓶)

    编程是很多偏计算机、人工智能领域必须掌握的一项技能,此编程能力在学习和工作中起着重要的作用。因此小白决定开辟一个新的板块“每日一题”,通过每天一道编程题目来强化...

    小白学视觉
  • c语言学习之数组3

    #include <stdio.h> int main() {   char cArr[] = {'I', 'L', 'O', 'V', 'E', 'C'};...

    py3study
  • 瓜子面经汇总

    HashMap是常用的Java集合之一,是基于哈希表的Map接口的实现。不支持同步和允许null作为key和value。

    武培轩
  • lnmp环境下如何手动备份网站文件和数据库

    我们站长做个网站都是挺不容易的,从域名注册,掌握虚拟主机或者 VPS 的基本配置,到安全防护,搭建网站、图片处理、发布文章,SEO 等等,是样样精通,不过这里面...

    魏艾斯博客www.vpsss.net
  • lnmp 如何备份网站文件和数据库

    魏艾斯博客www.vpsss.net

扫码关注云+社区

领取腾讯云代金券