| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1352871 | vahagng | Mobile (BOI12_mobile) | C++20 | 1099 ms | 159260 KiB |
#include <bits/stdc++.h>
using namespace std;
#define ld long double
struct Point{
ld x, y;
};
ld dist(Point A, Point B){
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
struct Line{
ld k, b;
Point X_intersect(){
return Point{-b / k * 1.0, 0.0};
}
};
Line ln(Point A, Point B){
// y1 = k*x1 + b
// y2 = k*x2 + b
// y1 - y2 = k(x1 - x2)
// k = (y1 - y2) / (x1 - x2)
ld K = (A.y - B.y) / (A.x - B.x);
ld BB = A.y - K*A.x;
return Line{K, BB};
}
Line mijnuxahayac(Point A, Point B){
auto [K, BB] = ln(A, B);
Point M = {(A.x + B.x) / 2.0, (A.y + B.y) / 2.0};
ld K1 = -1.0 / K;
ld BB1 = M.y - K1*M.x;
return Line{K1, BB1};
}
void precision(int x){
cout.setf(ios::fixed | ios::showpoint);
cout.precision(x);
return;
}
const int N = 1e6 + 10;
int n, l;
int main(){
cin >> n >> l;
map<ld,ld> mp;
precision(20);
for(int i = 1; i <= n; i++){
int x, y;
cin >> x >> y;
if(mp.find(x) != mp.end()){
if(abs(mp[x]) > abs(y)){
mp[x] = y;
}
}else{
mp[x] = y;
}
}
vector<Point> A;
for(auto i : mp){
// cerr << i.first << ' ' << i.second << endl;
A.push_back(Point{i.first, i.second});
}
if(A.size() == 1){
cout << max(dist(Point{0, 0}, A[0]), dist(Point{(ld)l, 0}, A[0])) << endl;
return 0;
}
vector<Point> pts;
int id = -1;
for(int i = 1; i < A.size(); i++){
Line L = mijnuxahayac(A[i - 1], A[i]);
Point X = L.X_intersect();
if(X.x < 0) continue;
if(id == -1){
id = i - 1;
}
pts.push_back(X);
}
// for(auto i : pts){
// cerr << i.x << ' ' << i.y << endl;
// }
if(id == -1){
cout << max(dist(Point{0, 0}, A.back()), dist(Point{(ld)l, 0}, A.back())) << endl;
return 0;
}
ld ans = 0;
for(int i = 0; i < pts.size(); i++){
if(i == 0){
// cerr << dist({0, 0}, A[id]) << endl;
// cerr << dist(pts[i], A[id]) << endl;
ans = max({ans, dist({0, 0}, A[id]), dist(pts[i], A[id])});
}else{
ans = max({ans, dist(pts[i - 1], A[id]), dist(pts[i], A[id])});
}
id++;
}
// cerr << dist(pts[pts.size() - 1], A[id]) << endl;
// cerr << dist({(ld)l, 0}, A[id]) << endl;
ans = max({ans, dist(pts[pts.size() - 1], A[id]), dist({(ld)l, 0}, A[id])});
cout << ans << endl;
}| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||
