UVA p920 Sunny Mountain

掃描線%%%

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<cmath>
#define min(x,y) (((x)>(y)) ? (y):(x))
#define max(x,y) (((x)>(y)) ? (x):(y))
using namespace std;
struct point{ int x, y;};
struct ccc{
bool operator()(point a, point b){return a.x < b.x;
}
}cccc;
int main()
{
int T;scanf("%d", &T);
while(T-->0){
int n; scanf("%d", &n);
point ps[200];
for(int lx = 0;lx < n;lx++)
scanf("%d %d", &ps[lx].x, &ps[lx].y);
sort(ps, ps+n , cccc);
double sum = 0;
double px = ps[n-1].x, py = ps[n-1].y;
for(int lx = n-2;lx >= 0;lx--){
if(ps[lx].y > py){
sum += (ps[lx].y-py) * sqrt( (ps[lx].x - ps[lx+1].x)*(ps[lx].x - ps[lx+1].x) +
(ps[lx].y - ps[lx+1].y)*(ps[lx].y - ps[lx+1].y))/(ps[lx].y-ps[lx+1].y);
py = ps[lx].y;
px = ps[lx].x;
}
}
printf("%.2f\n", sum);
}
return 0;
}