Submission #1604136
Source Code Expand
#include <cmath>
#include <vector>
#include <cstdio>
using int64 = long long;
struct point {
int64 x, y;
point(int64 a = 0, int64 b = 0): x(a), y(b) {}
point operator - (const point &rhs) const {
return point(x - rhs.x, y - rhs.y);
}
double norm() const {
return hypot(x, y);
}
};
int64 ccw(const point &a, const point &b, const point &c) {
return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}
int main() {
int n, st, ed;
scanf("%d%d%d", &n, &st, &ed);
point s(st, n), t(ed, 0);
std::vector<point> left, right;
for (int i = 0; i <= n; ++i) {
int l, r;
scanf("%d%d", &l, &r);
if (i == 0 || i == n) continue;
left.emplace_back(r, n - i);
right.emplace_back(l, n - i);
}
left.emplace_back(t);
right.emplace_back(t);
std::vector<point> lh = {s}, rh = {s};
double ret = 0;
point cur = s, last = s;
int leb = 0, reb = 0;
for (size_t i = 0; i < left.size(); ++i) {
while (lh.size() >= leb + 2 && ccw(lh[lh.size() - 2], lh.back(), left[i]) <= 0) lh.pop_back();
lh.push_back(left[i]);
while (rh.size() >= reb + 2 && ccw(rh[rh.size() - 2], rh.back(), right[i]) >= 0) rh.pop_back();
rh.push_back(right[i]);
while (ccw(cur, rh[reb + 1], lh[leb + 1]) < 0) {
ret += (cur - last).norm();
last = cur;
if (lh[leb + 1].y < rh[reb + 1].y) {
cur = rh[reb + 1];
++reb;
lh[leb] = cur;
} else {
cur = lh[leb + 1];
++leb;
rh[reb] = cur;
}
}
}
ret += (cur - last).norm() + (t - cur).norm();
printf("%.20f\n", ret);
return 0;
}
Submission Info
Submission Time |
|
Task |
D - レースゲーム |
User |
zimpha |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1657 Byte |
Status |
AC |
Exec Time |
52 ms |
Memory |
13660 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:24:32: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &st, &ed);
^
./Main.cpp:30:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &l, &r);
^
Judge Result
Set Name |
All |
Score / Max Score |
100 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample1.txt, 00_sample2.txt, 01_rnd_large_00.txt, 01_rnd_large_01.txt, 01_rnd_large_02.txt, 01_rnd_small_00.txt, 01_rnd_small_01.txt, 01_rnd_small_02.txt, 02_narrowrnd_large_00.txt, 02_narrowrnd_large_01.txt, 02_narrowrnd_small_00.txt, 02_narrowrnd_small_01.txt, 03_zigzag_large_00.txt, 03_zigzag_small_00.txt, 04_middle_large_00.txt, 04_middle_large_01.txt, 04_middle_large_02.txt, 04_middle_small_00.txt, 04_middle_small_01.txt, 04_middle_small_02.txt, 05_turnleft_large_00.txt, 05_turnleft_small_00.txt, 06_turnright_large_00.txt, 06_turnright_small_00.txt, 07_free_large_00.txt, 07_free_small_00.txt |
Case Name |
Status |
Exec Time |
Memory |
00_sample1.txt |
AC |
3 ms |
384 KB |
00_sample2.txt |
AC |
1 ms |
256 KB |
01_rnd_large_00.txt |
AC |
50 ms |
10972 KB |
01_rnd_large_01.txt |
AC |
50 ms |
9948 KB |
01_rnd_large_02.txt |
AC |
51 ms |
11100 KB |
01_rnd_small_00.txt |
AC |
1 ms |
256 KB |
01_rnd_small_01.txt |
AC |
1 ms |
256 KB |
01_rnd_small_02.txt |
AC |
1 ms |
256 KB |
02_narrowrnd_large_00.txt |
AC |
51 ms |
11484 KB |
02_narrowrnd_large_01.txt |
AC |
50 ms |
13404 KB |
02_narrowrnd_small_00.txt |
AC |
1 ms |
256 KB |
02_narrowrnd_small_01.txt |
AC |
1 ms |
256 KB |
03_zigzag_large_00.txt |
AC |
46 ms |
11484 KB |
03_zigzag_small_00.txt |
AC |
1 ms |
256 KB |
04_middle_large_00.txt |
AC |
51 ms |
12636 KB |
04_middle_large_01.txt |
AC |
51 ms |
11612 KB |
04_middle_large_02.txt |
AC |
50 ms |
9692 KB |
04_middle_small_00.txt |
AC |
1 ms |
256 KB |
04_middle_small_01.txt |
AC |
1 ms |
256 KB |
04_middle_small_02.txt |
AC |
1 ms |
256 KB |
05_turnleft_large_00.txt |
AC |
52 ms |
13660 KB |
05_turnleft_small_00.txt |
AC |
1 ms |
256 KB |
06_turnright_large_00.txt |
AC |
49 ms |
13532 KB |
06_turnright_small_00.txt |
AC |
1 ms |
256 KB |
07_free_large_00.txt |
AC |
41 ms |
8288 KB |
07_free_small_00.txt |
AC |
1 ms |
256 KB |