#include<bits/stdc++.h>
#define int long long
const int N=1014;
const double eps=1e-6;
using namespace std;
int cnt,head[N],vis[N];
double dis[N];
int n,m,xx,yy;
struct node
{
double dis;
int u;
node(){}
node(double Dis,int U){dis=Dis;u=U;}
bool operator >(const node a)const{return dis>a.dis;}
};
priority_queue<node,vector<node>,greater<node> >q;
struct person{
int x,y;
}a[N],b[N];
struct edge{
int to,next;
double w;
}ed[N*N];
bool check(int x1,int y1,int x2,int y2,int x0,int y0){
double k=double(y1-y2)/double(x1-x2);
double b=double(y1)-k*double(x1);
//cout<<k<<" "<<b<<endl;
//cout<<x0<<" "<<y0<<endl;
if(fabs(x0*k+b-y0)>eps) return true;
else if(x0>max(x1,x2)||x0<min(x1,x2)||y0>max(y1,y2)||y0<min(y1,y2))return true;
else return false;
}//检查是否能传球
double diss(int x1,int y1,int x2,int y2){
double x=double(x1-x2);
double y=double(y1-y2);
return sqrt(x*x+y*y);
}//距离
void add_edge(int u,int v,double w){
ed[++cnt].to=v;
ed[cnt].w=w;
ed[cnt].next=head[u];
head[u]=cnt;
};
void dijkstra(int st){
for(int i=1;i<=1000;i++){
dis[i]=99999999999;
}
//cout<<1145<<endl;
dis[st]=0;
q.push(node(0,st));
while(!q.empty()){
int u=q.top().u;
//cout<<u<<endl;
q.pop();
if(vis[u]) continue;
vis[u]=1;
for(int i=head[u];i;i=ed[i].next){
int v=ed[i].to,w=ed[i].w;
//cout<<v<<endl;
//cout<<dis[v]<<endl;
if(dis[v]>dis[u]+w){
dis[v]=dis[u]+w;
q.push(node(dis[v],v));
}
}
}
}
signed main(){
cin>>xx>>yy>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
for(int i=1;i<=m;i++){
cin>>b[i].x>>b[i].y;
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
bool flag=true;
for(int k=1;k<=m;k++) flag=check(a[i].x,a[i].y,a[j].x,a[j].y,b[k].x,b[k].y);
if(flag){
//cout<<i<<" "<<j<<endl;
add_edge(i,j,diss(a[i].x,a[i].y,a[j].x,a[j].y));
add_edge(j,i,diss(a[i].x,a[i].y,a[j].x,a[j].y));
}
}
}
for(int i=1;i<=n;i++){
//cout<<i<<endl;
add_edge(i,n+1,diss(a[i].x,a[i].y,xx,yy)*2);
}
dijkstra(1);
cout<<round(dis[n+1]);
return 0;
}
考虑是精度问题有一个点目标输出1119，实际输出1118
警钟撅烂，w的值应为double
1 个赞