Submission #5187
Source Code Expand
import std.stdio;
import std.math;
import std.algorithm;
class Point{
long x, y;
this(long x, long y){
this.x = x;
this.y = y;
}
Point opSub(Point p){
return new Point(x - p.x, y - p.y);
}
override bool opEquals(Object o){
return x == (cast(Point)o).x && y == (cast(Point)o).y;
}
}
long iprod(Point a, Point b){
return a.x * b.x + a.y * b.y;
}
long oprod(Point a, Point b){
return a.x * b.y - b.x * a.y;
}
long sq(long x){
return x * x;
}
long abs2(Point a){
return sq(a.x) + sq(a.y);
}
real getDistance(Point a){
return sqrt(cast(real)abs2(a));
}
real getDistance(Point a, Point b){
return getDistance(a - b);
}
int ccw(Point a, Point b, Point c){
auto nb = b - a, nc = c - a;
if( oprod(nb, nc) > 0 ){
return +1;
}
if( oprod(nb, nc) < 0 ){
return -1;
}
if( iprod(nb, nc) < 0 ){
return +2;
}
if( abs2(nb) < abs2(nc) ){
return -2;
}
return 0;
}
int N, start, goal;
Point[] ls, rs;
int[] lx, rx;
void init(){
scanf("%d%d%d", &N, &start, &goal);
ls = new Point[](N + 1);
rs = new Point[](N + 1);
lx = new int[](N + 1);
rx = new int[](N + 1);
for(int i=0; i<=N; ++i){
scanf("%d%d", &lx[i], &rx[i]);
ls[i] = new Point(lx[i], i);
rs[i] = new Point(rx[i], i);
}
}
//[from, to] : closed, ls[from] == rs[from], ls[to] == rs[to]
real calc(int from, int to){
if(to - from == 1){
return getDistance(ls[from], ls[to]);
}
Point cur = ls[from], tar = ls[to];
auto es = [cur];
for(int i=from+1; i<to; ++i){
if( ccw(cur, ls[i], tar) == +1 ){
es ~= ls[i];
cur = ls[i];
}
}
cur = rs[from];
for(int i=from+1; i<to; ++i){
if( ccw(cur, rs[i], tar) == -1 ){
es ~= rs[i];
cur = rs[i];
}
}
es ~= tar;
if(es.length == 2){
return getDistance(es[0], es[1]);
}
sort!"a.y < b.y"(es);
real ans = 0.0;
for(int i=0; i<es.length-1; ++i){
int y1 = cast(int)es[i].y, y2 = cast(int)es[i+1].y;
ls[y1] = rs[y1] = es[i];
ls[y2] = rs[y2] = es[i+1];
ans += calc(y1, y2);
}
return ans;
}
Point[] convexHullLeft(Point[] ps){
int n = cast(int)ps.length;
int k = 0;
Point[] ret = new Point[](2*n);
for(int i=0; i<n; ++i){
for(;k>1 && oprod(ret[k-1] - ret[k-2], ps[i] - ret[k-1]) <= 0; --k){}
ret[k++] = ps[i];
}
return ret[0..k];
}
Point[] convexHullRight(Point[] ps){
int n = cast(int)ps.length;
int k = 0;
Point[] ret = new Point[](2*n);
for(int i=0; i<n; ++i){
for(;k>1 && oprod(ret[k-1] - ret[k-2], ps[i] - ret[k-1]) >= 0; --k){}
ret[k++] = ps[i];
}
return ret[0..k];
}
real calcLeft(int from, int to, bool fin = false){
if(to - from == 1){
//writeln(ls[from].x, ",", ls[from].y, " -> ", ls[to].x, ",", ls[to].y);
return getDistance(ls[from], ls[to]);
}
/*
Point cur = ls[from], tar = ls[to];
auto es = [cur];
for(int i=from+1; i<to; ++i){
if( ccw(cur, ls[i], tar) == +1 ){
es ~= ls[i];
cur = ls[i];
}
}
es ~= tar;
*/
auto es = convexHullLeft(ls[from..to+1]);
/*
writeln("left: ", from, " ", to);
foreach(e ; es){
writeln(e.x, " ", e.y);
}
writeln;
*/
if(fin && es.length == 2){
//writeln(es[0].x, ",", es[0].y, " -> ", es[1].x, ",", es[1].y);
return getDistance(es[0], es[1]);
}
else{
real ans = 0.0;
for(int i=0; i<es.length-1; ++i){
int y1 = cast(int)es[i].y, y2 = cast(int)es[i+1].y;
ls[y1] = rs[y1] = es[i];
ls[y2] = rs[y2] = es[i+1];
ans += calcRight(y1, y2);
}
return ans;
}
}
real calcRight(int from, int to){
if(to - from == 1){
//writeln(rs[from].x, ",", rs[from].y, " -> ", rs[to].x, ",", rs[to].y);
return getDistance(rs[from], rs[to]);
}
/*
Point cur = rs[from], tar = rs[to];
auto es = [cur];
for(int i=from+1; i<to; ++i){
if( ccw(cur, rs[i], tar) == -1 ){
es ~= rs[i];
cur = rs[i];
}
}
es ~= tar;
*/
auto es = convexHullRight(rs[from..to+1]);
/*
writeln("right: ", from, " ", to);
foreach(e ; es){
writeln(e.x, " ", e.y);
}
writeln;
*/
if(es.length == 2){
//writeln(es[0].x, ",", es[0].y, " -> ", es[1].x, ",", es[1].y);
return getDistance(es[0], es[1]);
}
else{
real ans = 0.0;
for(int i=0; i<es.length-1; ++i){
int y1 = cast(int)es[i].y, y2 = cast(int)es[i+1].y;
ls[y1] = rs[y1] = es[i];
ls[y2] = rs[y2] = es[i+1];
ans += calcLeft(y1, y2, true);
}
return ans;
}
}
real bad_solver(){
long cx = start, cy = 0;
real ans = 0.0;
for(int i=1; i<N; ++i){
if(cx < lx[i]){
writeln(cx, ",", cy, " -> ", ls[i].x, ",", ls[i].y);
ans += getDistance(new Point(cx, cy), ls[i]);
cx = ls[i].x;
cy = ls[i].y;
}
else if(cx > rx[i]){
writeln(cx, ",", cy, " -> ", rs[i].x, ",", rs[i].y);
ans += getDistance(new Point(cx, cy), rs[i]);
cx = rs[i].x;
cy = rs[i].y;
}
}
writeln(cx, ",", cy, " -> ", rs[N].x, ",", rs[N].y);
ans += getDistance(new Point(cx, cy), rs[N]);
return ans;
}
real solve(){
ls[0] = rs[0] = new Point(start, 0);
ls[N] = rs[N] = new Point(goal, N);
//writeln(bad_solver);
return calcLeft(0, N);
//return calc(0, N);
//return min(bad_solver, bad_solver2, calc(0, N));
}
void main(){
init;
writefln("%.12f", solve);
}
Submission Info
Submission Time |
|
Task |
D - レースゲーム |
User |
komiya |
Language |
D (DMD 2.060) |
Score |
0 |
Code Size |
5293 Byte |
Status |
TLE |
Exec Time |
2035 ms |
Memory |
61352 KB |
Judge Result
Set Name |
all |
Score / Max Score |
0 / 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 |
18 ms |
820 KB |
00_sample2.txt |
AC |
18 ms |
128 KB |
01_rnd_large_00.txt |
AC |
1673 ms |
27788 KB |
01_rnd_large_01.txt |
AC |
1838 ms |
29572 KB |
01_rnd_large_02.txt |
AC |
1724 ms |
26892 KB |
01_rnd_small_00.txt |
AC |
23 ms |
128 KB |
01_rnd_small_01.txt |
AC |
23 ms |
1712 KB |
01_rnd_small_02.txt |
AC |
24 ms |
128 KB |
02_narrowrnd_large_00.txt |
AC |
1687 ms |
28868 KB |
02_narrowrnd_large_01.txt |
AC |
1631 ms |
33064 KB |
02_narrowrnd_small_00.txt |
AC |
24 ms |
128 KB |
02_narrowrnd_small_01.txt |
AC |
22 ms |
128 KB |
03_zigzag_large_00.txt |
TLE |
2033 ms |
61352 KB |
03_zigzag_small_00.txt |
AC |
191 ms |
3464 KB |
04_middle_large_00.txt |
AC |
1515 ms |
24448 KB |
04_middle_large_01.txt |
AC |
1604 ms |
23444 KB |
04_middle_large_02.txt |
AC |
1678 ms |
26528 KB |
04_middle_small_00.txt |
AC |
22 ms |
128 KB |
04_middle_small_01.txt |
AC |
24 ms |
0 KB |
04_middle_small_02.txt |
AC |
24 ms |
128 KB |
05_turnleft_large_00.txt |
TLE |
2035 ms |
54180 KB |
05_turnleft_small_00.txt |
AC |
20 ms |
1060 KB |
06_turnright_large_00.txt |
TLE |
2033 ms |
52880 KB |
06_turnright_small_00.txt |
AC |
20 ms |
0 KB |
07_free_large_00.txt |
AC |
357 ms |
25092 KB |
07_free_small_00.txt |
AC |
19 ms |
128 KB |