920.cpp

ACM University Valladolid 920

using namespace std;

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define EPS 1e-11
#define inf ( 1LL << 31 ) - 1
#define LL long long

#define _rep( i, a, b, x ) for( __typeof(b) i = ( a ); i <= ( b ); i += x )
#define rep( i, n ) for( __typeof(n) i = 0; i < ( n ); ++i )
#define rrep( i, a, b ) for( __typeof(b) i = ( a ); i >= ( b ); --i )
#define xrep( i, a, b ) for( __typeof(b) i = ( a ); i <= ( b ); ++i )

#define abs(x) (((x)< 0) ? (-(x)) : (x))
#define all(x) (x).begin(), (x).end()
#define ms(x, a) memset((x), (a), sizeof(x))
#define mp make_pair
#define pb push_back
#define sz(k) (int)(k).size()

typedef vector <int> vi;

// She
// May be the reason I survive
// The why and wherefore I'm alive
// The one I'll care for through the rough in ready years

//...

struct Pt
{
	int x, y;
	bool operator<(const Pt &a)const
	{
		if(x == a.x) return y<a.y;
		return x>a.x;
	}
	
}Mou[105];

double D(Pt &A, Pt &B)
{
	return (sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)));
}

int main()
{
	int tc, n;
	scanf("%d", &tc);
	rep(_, tc)
	{
		scanf("%d", &n);
		rep(i, n) scanf("%d %d", &Mou[i].x, &Mou[i].y);
		sort(Mou, Mou+n);
		
		int hiy = 0;
		double ans = 0;
		
		if (n == 1) ans = Mou[0].y;
		
		xrep(i, 1, n-1)
		{
			if (Mou[i-1].y < Mou[i].y)
			{
				double AB = D(Mou[i-1], Mou[i]);
				double AF = hiy-Mou[i].y;
				double AC = Mou[i-1].y - Mou[i].y;
				double AE = (AF/AC)*AB;
				hiy >?= Mou[i].y;
				if (AE < 0) continue;
				ans += AE;
			}
		}
		printf("%.2lf\n", ans);
	}
	
	return 0;
}