题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
https://blog.csdn.net/Dog_dream/article/details/82184221?ops_request_misc=%25257B%252522request%25255Fid%252522%25253A%252522161026947816780269833848%252522%25252C%252522scm%252522%25253A%25252220140713.130102334..%252522%25257D&request_id=161026947816780269833848&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduend~default-2-82184221.first_rank_v2_pc_rank_v29&utm_term=POJ2420
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=105;
#define eps 1e-5
#define inf 1e99
struct Node
{
double x,y;
void input()
{
scanf("%lf%lf",&x,&y);
}
}q[MAX_N];
int n;
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
double dist(Node a,Node b)
{
return sqrt(pow(abs(a.x-b.x),2)+pow((a.y-b.y),2));
}
double Getsum(double x,double y)
{
Node sta;
sta.x=x;
sta.y=y;
double sum=0;
for(int i=0;i<n;i++)
{
sum+=dist(sta,q[i]);
}
return sum;
}
int main()
{
while(cin>>n)
{
double x,y;
for(int i=0;i<n;i++)
{
q[i].input();
}
x=q[0].x;
y=q[0].y;
double t=1;
double ans=inf;
while(t>eps)
{
int flag=0;
for(int i=0;i<4;i++)
{
double tm=Getsum(x+dx[i]*t,y+dy[i]*t);
if(tm<ans)
{
ans=tm;
x+=dx[i]*t;
y+=dy[i]*t;
flag=1;
}
}
if(!flag)
{
t*=0.98;
}
}
printf("%0.f\n",ans);
}
}