제출 #1119509

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119509		awesomemaths	Mobile (BOI12_mobile)	C++17	0 / 100	455 ms	89752 KiB

mobile

using namespace std;
#include <bits/stdc++.h>
#define ld long double
#define ll long long
#define MAXN 305
#define ALPHABETSIZE 26
#define ff first
#define ss second
#define pii pair<long double,long double>
#define vi vector<long double>
#define vii vector<pair<long double,long double>>

ld figure(ld x1, ld y1, ld x2, ld y2)
{
    ld mx = (x1 + x2)/2;
    ld my = (y1 + y2)/2;
    //my = m * (mx) + b
    ld m = (x1 - x2)/(y2 - y1);
    ld b = my - m * mx;
    //cout << m << " " << b << "\n";
    ld ans = -1 * b/m;
    return ans;
}
ld dist(ld x1, ld y1, ld x2, ld y2)
{
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
int main()
{
    cout << fixed << setprecision(15);
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    ll n, l; cin >> n >> l;
    vector<pii> points(n);
    map<ld, ld> mp;
    for(int i = 0; i < n; i++){
        cin >> points[i].first >> points[i].second;
        points[i].second = abs(points[i].second);
    }
    stack<pair<ll, pair<ld, ld>>> s; 
    s.push({0, {0, l}});
    sort(points.begin(), points.end());
    for(int i = 1; i < n; i++){
        if(points[i].first == points[i - 1].first){
            continue;
        }
        ld curr = -1;
        if(points[i].second == points[i - 1].second){
            curr = (points[i].first + points[i - 1].first)/2;
        }
        else{
            curr = figure(points[i - 1].ff, points[i - 1].second, points[i].ff, points[i].ss);
        }
        while(s.size() && curr <= s.top().ss.ss){
            if(curr <= s.top().ss.ff){
                s.pop();
            }
            else{
                ld before = s.top().ss.ff;
                ll index = s.top().ff;
                s.pop();
                s.push({index, {before, curr}});
                s.push({i, {curr, l}});
                break;
            }
        }
    }
    ld res = 0;
    while(s.size()){
        auto get = s.top();
        s.pop();
        //cout << get.ff << " " << get.ss.ff << " " << get.ss.ss << "\n";
        res = max(res, dist(points[get.ff].first, points[get.ff].second, get.ss.ff,0));
        res = max(res, dist(points[get.ff].first, points[get.ff].second, get.ss.ss,0));
    }
    res = sqrt(res);
    cout << res << "\n";



}

• 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