题解如下
先说我的第一种早在很久以前就写过的思路
原题说的是几个点到两个点的最小距离和
所以我一开始就想那就把每个点到1,2号节点的比较,从最小里找最大的和就行了
代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int xa,ya,xb,yb;
int n;
int way1,way2;
int waya[100010],wayb[100010];
int s,z;
int main()
{
int x,y;
cin>>xa>>ya>>xb>>yb;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x>>y;
way1=pow(x-xa,2)+pow(y-ya,2);
way2=pow(x-xb,2)+pow(y-yb,2);
if(way1<way2)
{
waya[++s]=way1;
}
else
{
wayb[++z]=way2;
}
}
sort(waya+1,waya+1+s);
sort(wayb+1,wayb+1+z);
cout<<waya[s]+wayb[z];
return 0;
然后
最后老老实实写搜索
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
int ans=0x3f3f3f3f;
int max2;
int xa,ya,xb,yb;
struct node{
int x,y,c;
}map[100010];
int poww(int a,int b)
{
int x,y;
if(b==1)
{
x=xa,y=ya;
}
if(b==2)
{
x=xb,y=yb;
}
return pow(x-map[a].x,2)+pow(y-map[a].y,2);
}
bool cmp(node a,node b)
{
return a.c>b.c;
}
int main()
{
cin>>xa>>ya>>xb>>yb;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>map[i].x>>map[i].y;
map[i].c=poww(i,1);
}
// if(n==1)
// {
// cout<<min(poww(0,1),poww(0,2));
// return 0;
// }(无脑特判)
sort(map,map+n,cmp);//从大到小排列 map
ans=map[0].c;
int way2=0;
for(int i=1;i<=n;i++)
{
way2=max(way2,poww(i-1,2));
ans=min(ans,way2+map[i].c);//
}
cout<<ans;
return 0;
}
完了
共 1 条回复
前排点赞