NEERC2012 - C - Caravan Robbers.cpp

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int> point;
const int MAXN=100000+10;

struct Seg {
	int l, r;
	Seg() {}
	Seg(int l, int r):l(l), r(r) {}
	bool operator <(const Seg &t) const {
		return (l<t.l);
	}
	LL operator * (const Seg oth) {
		return (LL)l*oth.r-(LL)r*oth.l;
	}
	Seg operator - (const Seg oth) {
		return Seg(l-oth.l, r-oth.r);
	}
};

struct Frac {
	LL n, d;
	Frac() {}
	Frac(LL _n, LL _d):n(_n),d(_d) {fix();}
	bool operator<(const Frac t) const {
		return n*t.d<d*t.n;
	}
	void fix() {
		LL t=__gcd(n, d);
		n/=t; d/=t;
	}
	void out() {
		cout << n << '/' << d << endl;
	}
};

Seg A[MAXN], S[MAXN];
int N;

int main() {
	freopen("caravan.in", "r", stdin);
	freopen("caravan.out", "w", stdout);
	scanf("%d", &N);
	for (int i=0; i<N; i++) scanf("%d%d", &A[i].l, &A[i].r);
	sort(A, A+N);
	int head=0, tail=-1;
	Frac ans=Frac(10000000, 1);
	for (int i=0; i<N; i++) {
		S[++tail]=Seg(i, A[i].l);
		while (head+2<=tail&&((S[tail-1]-S[tail-2])*(S[tail]-S[tail-1])>=0)) S[--tail]=Seg(i, A[i].l);
		Seg ttt=Seg(i+1, A[i].r);
		while (head<tail&&((ttt-S[head])*(S[head+1]-S[head])>=0)) head++;
		Frac tmp=Frac(A[i].r-S[head].r, i-S[head].l+1);
		if (tmp<ans) ans=tmp;
	}
	ans.out();
	fclose(stdin); fclose(stdout);
	return 0;
}