Submission #1083622

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083622		codexistent	Mobile (BOI12_mobile)	C++14	0 / 100	692 ms	57240 KiB

mobile

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define MAXN 1000005
#define FOR(i, a, b) for(ll i = a; i <= b; i++)
#define f first
#define s second

ll n;
db l;
vector<pair<db, db>> s;

bool overlap(pair<db, db> a, pair<db, db> b){ // does a overlap b vertex?
    db ad = (a.f - b.f) * (a.f - b.f) + a.s * a.s;
    db bd = b.s * b.s;

    return ad <= bd;
}

db overlap2(pair<db, db> a, pair<db, db> b){
    db x = (a.f * a.f + a.s * a.s - b.f * b.f - b.s * b.s) / (2 * (a.f - b.f));
    // cout << " HERE: " << x << endl;
    x = max((db)0, x);
    x = min(x, l);
    return min(sqrt((a.f - x) * (a.f - x) + a.s * a.s), sqrt((b.f - x) * (b.f - x) + b.s * b.s));
}

int main(){
    cin >> n >> l;
    FOR(i, 1, n){
        db x, y; cin >> x >> y;
        s.push_back({x, y});
    }
    sort(begin(s), end(s));

    vector<pair<db, db>> s2;
    ll prv = -1;
    FOR(i, 0, n - 1){
        if(prv == -1 || i == n - 1 || !(overlap(s[prv], s[i]) && overlap(s[i + 1], s[i]))){
            s2.push_back(s[i]);
            prv = i;
        }
    }

    db r = max(sqrt(s2[0].f * s2[0].f + s2[0].s * s2[0].s), sqrt((s2.back().f - l) * (s2.back().f - l) + s2.back().s * s2.back().s));
    // cout << "START PT IS " << (s2[0].f * s2[0].f + s2[0].s * s2[0].s) << endl;
    // cout << "END PT IS " << ((s2.back().f - l) * (s2.back().f - l) + s2.back().s * s2.back().s) << endl;
    FOR(i, 0, s2.size() - 2){
        r = max(r, overlap2(s2[i], s2[i + 1]));
    }

    cout << fixed << setprecision(6) << r;
}

Compilation message (stderr)

mobile.cpp: In function 'int main()':
mobile.cpp:6:38: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<double, double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define FOR(i, a, b) for(ll i = a; i <= b; i++)
......
   49 |     FOR(i, 0, s2.size() - 2){
      |         ~~~~~~~~~~~~~~~~~~~           
mobile.cpp:49:5: note: in expansion of macro 'FOR'
   49 |     FOR(i, 0, s2.size() - 2){
      |     ^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 5
• Subtask 8: 0 / 5
• Subtask 9: 0 / 5
• Subtask 10: 0 / 5
• Subtask 11: 0 / 5
• Subtask 12: 0 / 5
• Subtask 13: 0 / 5
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5
• Subtask 20: 0 / 5
• Subtask 21: 0 / 5