C++(g++ 7.5.0) 解法, 执行用时: 400ms, 内存消耗: 3736K, 提交时间: 2022-09-03 18:22:35

#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define int long long
using namespace std;
const int _=1e6+7;
// const int mod=998244353;
int read() {
    int x=0,f=1;char s=getchar();
    for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;
    for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';
    return x*f;
}
struct point {
	int x,y;
	point operator - (const point &p) const {
		return point{x-p.x,y-p.y};
	}
	int operator * (const point &p) const {
		return x*p.y-y*p.x;
	}
};
double distance(point a,point b) {
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int n,cnt;
point p[_];
array<point,2> line[_];
double dis[700][700];
signed main() {
	#ifdef ONLINE_JUDGE
	#else
	    freopen("a.in","r",stdin);
	    // freopen("a.out","w",stdout);
	#endif
	n=read(),n=read(),n=read();
	FOR(i,1,n+1) {
		point a,b;
		a.x=read(),a.y=read();
		b.x=read(),b.y=read();
		line[i]={a,b};
		p[++cnt]=a;
		p[++cnt]=b;
	}
	FOR(i,1,cnt) FOR(j,1,cnt) dis[i][j]=1e18;
    FOR(i,1,cnt) {
    	FOR(j,i+1,cnt) {
    		auto a=p[i],b=p[j];
    		int flag=0;
    		FOR(k,1,n) {
    			auto [c,d] = line[k];
    			if(((b-a)*(c-a))*((b-a)*(d-a))<0&&
    			   ((d-c)*(b-c))*((d-c)*(a-c))<0) {
    				flag=1;
    				break;
    			}
    		}
    		if(flag==0) dis[i][j]=dis[j][i]=distance(a,b);
    		// if(i==j-1) {
    			// cout<<dis[i][j]<<"!\n";
    		// }
    	}
    	dis[i][i]=0;
    }
    FOR(i,1,cnt) {
    	FOR(j,1,cnt) {
    		if(i==j) continue;
    		FOR(k,1,cnt) {
    			if(j==k||i==k) continue;
    			dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
    		}
    	}
    }
    printf("%.4f",dis[cnt-1][cnt]);

    return 0;
}

C++(clang++11) 解法, 执行用时: 136ms, 内存消耗: 860K, 提交时间: 2020-10-25 14:03:39

#include<bits/stdc++.h>

using namespace std;
#define ll long long

const int N = 610;
int n, m, k, tmp[N];
double d[N];
bool vis[N], e[N][N];
struct item{
	int x, y;
	void read(){ scanf("%d%d", &x, &y);}
	item operator-(const item &r)const{ return (item){x-r.x, y-r.y};}
	int operator^(const item &r)const{ return x*r.y-y*r.x;}
} a[N];
double dis(const item &a, const item &b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int main() {
	scanf("%d%d%d", &n, &m, &k);
	for(int i=1; i<=k; ++i) a[i*2-1].read(), a[i*2].read();
	a[k*2+1].read(), a[k*2+2].read();
	for(int i=1; i<=k; ++i){
		for(int j=1; j<=k*2+2; ++j) tmp[j]=((a[i*2]-a[i*2-1])^(a[j]-a[i*2-1]));
		for(int j=1; j<=k*2+2; ++j) if(tmp[j]<=0) for(int t=1; t<=k*2+2; ++t) if(tmp[t]>0){
			if(((a[j]-a[i*2-1])^(a[t]-a[i*2-1]))>0 && ((a[t]-a[i*2])^(a[j]-a[i*2]))>0)
				e[j][t]=e[t][j]=1;
		}
	}
	fill(d+1, d+k*2+3, 1e10);
	d[k*2+1]=0;
	for(int i=1; i<=k*2+2; ++i){
		int mn=0;
		for(int j=1; j<=k*2+2; ++j) if(!vis[j] && (!mn || d[j]<d[mn])) mn=j;
		vis[mn]=1;
		for(int j=1; j<=k*2+2; ++j) if(!vis[j] && !e[j][mn]) d[j]=min(d[j], d[mn]+dis(a[j], a[mn]));
	}
	printf("%.4lf\n", d[k*2+2]);
	return 0;
}