Submission #6542626


Source Code Expand

#include <stdio.h>
#include <math.h>
#include <deque>
using namespace std;

struct point { int x, y; };

long long ccw(long long a, long long b, long long c, long long d, long long e, long long f)
{
	return a * (d - f) + c * (f - b) + e * (b - d);
}

long long ccw(point a, point b, point c)
{
	return ccw(a.x, a.y, b.x, b.y, c.x, c.y);
}

double go(point a, point b)
{
	return hypot(a.x - b.x, a.y - b.y);
}

double len;
void push(deque<point> &l, deque<point> &r, point p, int c)
{
	int s = r.size();
	while (s > 1 && ccw(r[s - 2], r[s - 1], p) * c >= 0) r.pop_back(), s--;

	if (r.size() == 1)
	{
		while (l.size() > 1 && ccw(l[0], l[1], p) * c >= 0)
		{
			len += go(l[0], l[1]);
			l.pop_front();
		}
		r[0] = l[0];
	}
	r.push_back(p);
}

int main()
{
	deque<point> l, r;

	int n, s, e;
	scanf("%d %d %d", &n, &s, &e);
	l.push_back({ 0, s });
	r.push_back({ 0, s });

	for (int i = 0; i <= n; i++){
		int p, q;
		scanf ("%d %d", &p, &q);
		if (0 < i && i < n){
			push(l, r, { i, p }, +1);
			push(r, l, { i, q }, -1);
		}
	}
	push(l, r, { n, e }, +1);

	for (int i = 1; i < r.size(); i++) len += go(r[i - 1], r[i]);

	printf("%.12lf\n", len);

	return 0;
}

Submission Info

Submission Time
Task D - レースゲーム
User luogu_bot1
Language C++ (GCC 5.4.1)
Score 100
Code Size 1228 Byte
Status AC
Exec Time 48 ms
Memory 256 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:47:14: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
  l.push_back({ 0, s });
              ^
./Main.cpp:47:22: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
  l.push_back({ 0, s });
                      ^
./Main.cpp:48:14: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
  r.push_back({ 0, s });
              ^
./Main.cpp:48:22: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
  r.push_back({ 0, s });
                      ^
./Main.cpp:54:15: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
    push(l, r, { i, p }, +1);
               ^
./Main.cpp:55:15: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11
    push(r, l, { i, q }, -1);
               ^
./Main.cpp:58:13: warning: extended initializer lists only available with -std=c++11 or -std=gnu++11...

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 1 ms 256 KB
00_sample2.txt AC 1 ms 256 KB
01_rnd_large_00.txt AC 48 ms 256 KB
01_rnd_large_01.txt AC 48 ms 256 KB
01_rnd_large_02.txt AC 48 ms 256 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 47 ms 256 KB
02_narrowrnd_large_01.txt AC 47 ms 256 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 41 ms 256 KB
03_zigzag_small_00.txt AC 1 ms 256 KB
04_middle_large_00.txt AC 48 ms 256 KB
04_middle_large_01.txt AC 48 ms 256 KB
04_middle_large_02.txt AC 48 ms 256 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 46 ms 256 KB
05_turnleft_small_00.txt AC 1 ms 256 KB
06_turnright_large_00.txt AC 45 ms 256 KB
06_turnright_small_00.txt AC 1 ms 256 KB
07_free_large_00.txt AC 39 ms 256 KB
07_free_small_00.txt AC 1 ms 256 KB