枚举小数据(20pts)

• 如果只有一枚导弹就选近的，如果是两枚则分情况讨论，
  • 第一套工作系统控制a,b,
  • 第一套工作系统控制a，第二套系统控制b，
  • 第一套控制b，第二套控制a
  • 第二套控制a,b 然后找到这四种情况的最小值

#include<bits/stdc++.h>
using namespace std;
int cal(int x1,int y1,int x2,int y2) //计算距离平方和
{
	int dx=x2-x1;
	int dy=y2-y1;
	return dx*dx+dy*dy;
} 
int main()
{
	int x1,y1,x2,y2;
	cin>>x1>>y1>>x2>>y2;
	int n;
	cin>>n;
	if(n==1)
	{
		int a1,b1;
		cin>>a1>>b1;
		cout<<max(a1,b1)<<endl;
	}
	else if(n==2)
	{
		int a1,b1,a2,b2;
		cin>>a1>>b1>>a2>>b2;
		int s[4];
		s[0]=cal(x1,y1,a1,b1)+cal(x1,y1,a2,b2);
		s[1]=cal(x1,y1,a1,b1)+cal(x2,y2,a2,b2);
		s[2]=cal(x2,y2,a1,b1)+cal(x1,y1,a2,b2);
		s[3]=cal(x2,y2,a1,b1)+cal(x2,y2,a2,b2);
		sort(s,s+4);
		cout<<s[0]<<endl;
	}
    return 0;
}

枚举+贪心(排序)(100pts)

• 算法分析，通过画图容易发现主要是枚举两个工作系统的半径，且当左边半径$r_1$确定以后，所有小于等于$r_1$的导弹一定都可以在左边，而且右边的半径就是所有没有覆盖的最大距离的平方和。
• 那么我们就可以通过将所有的导弹到第一个系统的半径平方和从大到小排序，然后依次枚举每个点，那么已经枚举的点都是由右边控制的，还未枚举的点都是由左边控制的。

#include<bits/stdc++.h>
using namespace std;
const int N=100010;
int n;
int a1,b1,a2,b2;
struct Point{
    int x,y;
    int d;
}point[N];
int cal(int x1,int y1,int x2,int y2) //计算距离平方和
{
    int dx=x1-x2;
    int dy=y1-y2;
    return dx*dx+dy*dy;
}
bool cmp(Point a,Point b) //按照距离平方和从大到小排序
{
    if(a.d>b.d) return true;
    return false;
}
int main()
{
    cin>>a1>>b1>>a2>>b2;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        point[i]={x,y,cal(x,y,a1,b1)};
    }
    sort(point,point+n,cmp);
    int res=point[0].d; //初始化的时候所有的点都在左边
    int r=0;
    for(int i=1;i<=n;i++)
    {
        r=max(r,cal(point[i-1].x,point[i-1].y,a2,b2)); //每次移动一个点到右边,得到右边的最大子
        res=min(res,point[i].d+r); //更新答案
    }
    cout<<res;
    return 0;
}