Intelligent Robot

链接：https://ac.nowcoder.com/acm/contest/7501/B
思路：
只考虑特殊点即墙的端点，起点和终点。对于每个点都与另外的所有点尝试建边，建边的条件是这个边不会穿过墙。那么最后跑个最短路即可。
代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 610;

int head[maxn], tot;
double d[maxn];
bool vis[maxn];

struct Point
{
    double x,y;
    Point(){}
    //定义运算 
    Point(double _x,double _y){x = _x;y = _y;}
    Point operator + (const Point &b)const{
        return Point(x+b.x,y+b.y);
    }
    Point operator - (const Point &b)const{
        return Point(x-b.x,y-b.y);
    }
    Point operator * (const double &k)const{//乘常数
        return Point(x*k,y*k);
    }
    Point operator / (const double &k)const{
        return Point(x/k,y/k);
    }
    //点的叉积和点积都是数
    //点积
    double operator * (const Point &b)const{
        return x*b.x+y*b.y;
    }
    //叉积
    double operator ^ (const Point &b)const{
        return x*b.y-y*b.x;
    }

    double powlen(){return x*x+y*y;};

    double len(){return sqrt(powlen());}
}sta, ed;

inline double dis(Point p1,Point p2) {
    return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}

struct Line{
    Point a, b;
    Line(){}
    Line(Point p1, Point p2) {
        this -> a = p1;
        this -> b = p2;
    }
    double Len() {
        return dis(a, b);
    }
}a[maxn];

struct Node{
    int u, v, nxt;
    double w;
}e[maxn * maxn];

struct A{
    int pos;
    double cost;
    bool operator < (const A &a1)const{
        return cost > a1.cost;
    }
};
int n, m, k;

bool judge(Line line) {
    for(int i = 1; i <= k; i++) {
        Point AB = line.b - line.a;
        Point AC = a[i].a - line.a;
        Point AD = a[i].b - line.a;

        Point CD = a[i].b - a[i].a;
        Point CB = line.b - a[i].a;
        Point CA = line.a - a[i].a;
        if((AB^AC)*(AB^AD) < 0 && (CD^CB)*(CD^CA) < 0) return true;
    }
    return false;
}


inline void add(int x, int y, double z)
{
    e[++tot].u = x;
    e[tot].v = y;
    e[tot].w = z;
    e[tot].nxt = head[x];
    head[x] = tot;
}

void dij(int src)
{
    for(int i = 0; i < 610; i++) d[i] = 1e18;
    memset(vis, 0, sizeof(vis));
    priority_queue<A>q;
    d[src] = 0;
    A now;
    now.cost = 0;
    now.pos = src;
    q.push(now);
    while(!q.empty())
    {
        now = q.top();
        q.pop();
        if(vis[now.pos])
            continue;
        vis[now.pos] = 1;
        for(int i = head[now.pos]; ~i; i = e[i].nxt)
        {
            int to = e[i].v;
            if(!vis[to] && d[to] > e[i].w + d[e[i].u])
            {
                d[to] = d[e[i].u] + e[i].w;
                now.cost = d[to];
                now.pos = to;
                q.push(now);
            }
        }
    }
}

int main()
{
    memset(head, -1, sizeof(head));
    vector<Point> vec;
    scanf("%d%d%d",&n,&m,&k);
    for(int i = 1; i <= k; i++){
        Point p1, p2;
        scanf("%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y);
        a[i].a = p1; a[i].b = p2;
    }
    scanf("%lf%lf%lf%lf",&sta.x,&sta.y,&ed.x,&ed.y);
    vec.push_back(sta);
    for(int i = 1; i <= k; i++) {
        vec.push_back(a[i].a);
        vec.push_back(a[i].b);
    }
    vec.push_back(ed);
    int sz = vec.size();
    for(int i = 0; i < sz; i++) {
        for(int j = i+1; j < sz; j++) {
            Line line = Line(vec[i], vec[j]);
            if(!judge(line)) {
                double len = dis(vec[i], vec[j]);
//                cout << i << " " << j << " " <<len << endl;
                add(i, j, len);
                add(j, i, len);
            }
        }
    }
    dij(0);
    printf("%.4f\n",d[vec.size()-1]);

    return 0;
}