「JoyOI1551」平衡的爱

描述 Description

问题描述
milesian在你的帮助下（假设你把第一题AC了~）终于摆脱了女生的诱惑。但是女生们又缠上了另外一个帅哥——taring。但是taring保持清醒的方式不同，他会选择同时和所有女生聊天。这时，所有女生，还有taring，都站在牛顿广场上。且这种诱惑能量，是一个向量。满足向量定理。这个力为Fi，现在taring，站在高台上，希望找一个点，使他所受的诱惑能量和（向量和）为0。注意，他可以选择和某一个点的女生相吻在一起。这时他所受的这个女生的诱惑能量为0（因为女生被吻的时候，头脑是一片空白）。求这个点的横纵坐标。

这个问题的化简：给定一个2维平面,平面上有N个村庄,每个村庄有f[i]个人,你需要选择一个地方建造医院,使得所有人到医院的总距离最小

输入格式 InputFormat

第一行为一个正整数N，表示女生个数
以下N行，每行有三个整数Xi，Yi，Fi。分别表示第i个女生的横坐标，纵坐标，能量的大小
(0<N<=1000,-1000<=XI,YI<=1000,sum(Fi)<=maxlongint)

输出格式 OutputFormat

两个实数，为帮taring选择的横坐标和纵坐标（保留小数点后两位）
保证输出答案唯一

样例输入 SampleInput [复制数据]

1

2

3

4

5

4

0 0 10

3 0 10

0 3 10

1 1 1

样例输出 SampleOutput [复制数据]

0.74 0.74

1

0.74 0.74

数据范围和注释 Hint

N<=1000;-1000<=xi，yi<=1000
fi不超过maxlongint
并且保证标量和不超过maxlongint

题解

本题就是每个点多了一个权值。。直接写个爬山然后直接每次算都乘一个权值就好了。。

不过似乎精度比较坑。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n;
double xx,yy,ans,t;
double ansx,ansy;
struct point{double x,y;int v;}p[1005];
double sqr(double x){return x*x;}
double dis(double x,double y,point p)
{return sqrt(sqr(x-p.x)+sqr(y-p.y));}
double getsum(double x,double y)
{
    double tmp=0;
    for(int i=1;i<=n;i++)
        tmp+=p[i].v*dis(x,y,p[i]);
    return tmp;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        xx=yy=0;ans=1e20;t=10000;
        for(int i=1;i<=n;i++)
        {
            scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].v);
            xx+=p[i].v*p[i].x;yy+=p[i].v*p[i].y;
        }
        xx/=n;yy/=n;
        ans=getsum(xx,yy);
        double tmp,x,y;
        while(t>0.0000001)
        {
            x=y=0;
            for(int i=1;i<=n;i++)
            {
                x+=p[i].v*(p[i].x-xx)/dis(xx,yy,p[i]);
                y+=p[i].v*(p[i].y-yy)/dis(xx,yy,p[i]);
            }
            tmp=getsum(xx+x*t,yy+y*t);
            if(tmp<ans){ans=tmp;xx+=x*t;yy+=y*t;ansx=xx;ansy=yy;}
            t*=0.9;
        }
        printf("%.2lf %.2lf\n",ansx,ansy);
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

#include<iostream>

#include<cstdio>

#include<cmath>

using namespace std;

int n;

double xx,yy,ans,t;

double ansx,ansy;

struct point{double x,y;int v;}p[1005];

double sqr(double x){return x*x;}

double dis(double x,double y,point p)

{return sqrt(sqr(x-p.x)+sqr(y-p.y));}

double getsum(double x,double y)

{

double tmp=0;

for(int i=1;i<=n;i++)

tmp+=p[i].v*dis(x,y,p[i]);

return tmp;

}

int main()

{

while(scanf("%d",&n)!=EOF)

{

xx=yy=0;ans=1e20;t=10000;

for(int i=1;i<=n;i++)

{

scanf("%lf%lf%d",&p[i].x,&p[i].y,&p[i].v);

xx+=p[i].v*p[i].x;yy+=p[i].v*p[i].y;

}

xx/=n;yy/=n;

ans=getsum(xx,yy);

double tmp,x,y;

while(t>0.0000001)

{

x=y=0;

for(int i=1;i<=n;i++)

{

x+=p[i].v*(p[i].x-xx)/dis(xx,yy,p[i]);

y+=p[i].v*(p[i].y-yy)/dis(xx,yy,p[i]);

}

tmp=getsum(xx+x*t,yy+y*t);

if(tmp<ans){ans=tmp;xx+=x*t;yy+=y*t;ansx=xx;ansy=yy;}

t*=0.9;

}

printf("%.2lf %.2lf\n",ansx,ansy);

}

return 0;

}

hzwer.com _ Home | http://hzwer.com

描述 Description

输入格式 InputFormat

输出格式 OutputFormat

样例输入 SampleInput [复制数据]

样例输出 SampleOutput [复制数据]

数据范围和注释 Hint

分类目录

热门文章

Myfriends

近期评论