Cod sursa(job #3252993)

Utilizator Tudor06MusatTudor Tudor06 Data 31 octombrie 2024 17:38:32
Problema Cele mai apropiate puncte din plan Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin( "cmap.in" );
ofstream fout( "cmap.out" );

const int NMAX = 1e5;
long double alfa = 0.69;

pair <long double, long double> rotate( pair <long double, long double> p ) {
    long double costel = cos(alfa), sinel = sin(alfa), x = p.first, y = p.second;
    return {x * costel - y * sinel, y * costel + x * sinel};
}

set <pair<long double, long double>> st;

long long dist( pair <long double, long double> a, pair <long double, long double> b ) {
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second) + 0.5;
}
pair <long double, long double> v[NMAX];

void solve() {
    int n, cnt = 0;
    long long ans = 4e18;
    fin >> n;
    cout << n << endl;
    for ( int i = 0; i < n; i ++ ) {
        fin >> v[i].first >> v[i].second;
        v[i] = rotate( v[i] );
    }
    st.insert( v[0] );
    for ( int i = 1; i < n; i ++ ) {
        st.insert( v[i] );
        auto poz = st.lower_bound( v[i] );
        auto a = next(poz);
        while ( a != st.end() && (*a).first - v[i].first <= ans ) {
            ans = min( ans, dist( *a, v[i] ) );
            a = next(a);
            cnt ++;
        }
        a = poz;
        while ( a != st.begin() && v[i].first - (*prev(a)).first <= ans ) {
            ans = min( ans, dist( *prev(a), v[i] ) );
            a = prev(a);
            cnt ++;
        }
    }
    fout << fixed << setprecision( 7 ) << sqrtl( ans ) << '\n';
}
int main() {
    //ios_base::sync_with_stdio( false );
    //cin.tie( NULL );
    //cout.tie( NULL );
    int t = 1;
    //cin >> t;
    while ( t-- ) solve();
    return 0;
}