导弹拦截

2020we 2022-03-14 18:43:48 2022-03-14 19:15:03

题解如下

原题

分享画图2.0

先说我的第一种早在很久以前就写过的思路

原题说的是几个点到两个点的最小距离和

所以我一开始就想那就把每个点到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 条回复

Mrnobody

前排点赞