Cod sursa(job #2211060)

Utilizator felixiPuscasu Felix felixi Data 9 iunie 2018 12:09:32
Problema Ubuntzei Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("cerc3.in");
ofstream out("cerc3.out");

const int NMAX = 2000;

struct Cerc
{
    int x,y,r;
};

int N;
Cerc v[NMAX+2];
map<pair<int,int>, vector<Cerc>> linii;

void afis(const vector<pair<double, double>> &vec)
{
    for( auto x : vec ) cout << x.first << ' ' << x.second << " | ";
    cout << '\n';
}

pair<int,int> get_linie(Cerc c)
{
    int gc = __gcd(c.x, c.y);
    c.x /= gc;
    c.y /= gc;
    return {c.x, c.y};
}

double dist(int x, int y)
{
    return sqrt(x*x + y*y);
}

vector<pair<double, double>> get_delim(const vector<Cerc> &cercuri, pair<int,int> linie)
{
    vector<pair<double, double>> sol;
    for( const auto &pp : cercuri ) {
        double delta = pp.x * pp.r / dist(pp.x, pp.y);
        sol.push_back({-delta + pp.x, +delta + pp.x});
    }
    return sol;
}

int problema_spectacolelor(vector<pair<double, double>> interv)
{
    sort(interv.begin(), interv.end());
    ///afis(interv);
    reverse(interv.begin(), interv.end());
    int cnt = 0;
    double last = (1 << 30);
    for( auto pp : interv ) {
        if( pp.second < last ) {
            last = pp.first;
            ++cnt;
        }
    }
    return cnt;
}

int main()
{
    cout << fixed << setprecision(3);
    in >> N;
    for( int i = 1;  i <= N;  ++i ) {
        in >> v[i].x >> v[i].y >> v[i].r;
        linii[ get_linie(v[i]) ].push_back(v[i]);
    }
    int best = 0, cnt = 0;
    for( auto pp : linii ) {
        auto cercuri = pp.second;
        auto linie = pp.first;
        auto intervale = get_delim(cercuri, linie);
        int concurrent = problema_spectacolelor(intervale);
        if( concurrent > best )
            best = concurrent, cnt = 0;
        cnt += (best == concurrent);
    }
    out << linii.size() << ' ' << best << ' ' << cnt << '\n';
    return 0;
}