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
AC × 26
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