Cod sursa(job #2083307)

Utilizator VoineaAndreiVoinea Ioan-Andrei VoineaAndrei Data 7 decembrie 2017 15:22:54
Problema Adapost 2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include<bits/stdc++.h>
using namespace std;

ifstream f("adapost2.in");
ofstream g("adapost2.out");

//structul pozitiei unui soldat
struct soldat{
    double x;
    double y;
};

int n;
double x,y,fort_x,fort_y;

//vector de soldati
vector<soldat>v(50005);

//calculeaza distanta intre 2 puncte
double dist(double x1, double y1, double x2, double y2){
    return sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2 -y1));
}

//calculam suma distantelor soldatilor pana la fort
double dist_fort(double x, double y){
    double sum_dist=0;
    for (int i=1;i<=n;++i)
        sum_dist+=dist(x,y,v[i].x,v[i].y);
    return sum_dist;
}

int main(){
    f>>n;
    for (int i=1;i<=n;++i){
        f>>x>>y;
        v[i] = {x*1000.0,y*1000.0}; //pentru a nu pierde din precizie
        fort_x+=v[i].x;
        fort_y+=v[i].y;
    }

    //incepem cu pozitia medie dintre toate pozitiile
    fort_x/=(double)n; fort_y/=(double)n;

    //suma distantelor soldatilor pana la fort
    //cu cat suma e mai mica cu atat fortule intr-o pozitie optima
    double curr_dis=dist_fort(fort_x,fort_y);

    //stabilim un pas cu care se modifica valorile ce pot fi mai bune
    double pas=100000.000;
    while (pas>=1){

        //alegem 4 pozitii ce pot fi mai bune ca pozitia fortului
        double dr=dist_fort(fort_x+pas,fort_y);
        double st=dist_fort(fort_x-pas,fort_y);
        double sus=dist_fort(fort_x,fort_y+pas);
        double jos=dist_fort(fort_x,fort_y-pas);

        //apoi le comparam si mutam fortul
        if (dr<curr_dis){
            curr_dis=dr;
            fort_x+=pas;
        }
        else if (st<curr_dis){
            curr_dis=st;
            fort_x-=pas;
        }
        else if (sus<curr_dis){
            curr_dis=sus;
            fort_y+=pas;
        }
        else if (jos<curr_dis){
            curr_dis=jos;
            fort_y-=pas;
        }
        else
            pas *= 0.4; //raportul cu care se modifica pasul daca nu s-au gasit pozitii mai bune
    }

    //reintoarcem numerele la precizia initiala
    fort_x/=1000.0; fort_y/=1000.0;
    g<<fort_x<<" "<<fort_y;
}