Submission #5186

---

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){
	const int n = 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){
	const int n = 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

Compile Error

./Main.d(121): Error: cannot implicitly convert expression (ps.length) of type ulong to const(int)
./Main.d(132): Error: cannot implicitly convert expression (ps.length) of type ulong to const(int)