省赛Colorful Rainbows

#include <iostream> #include <string.h> #include <algorithm> #include <math.h> #include <stdio.h> using namespace std; struct straight{ double a, b; }Lu[6000], Hui[6000]; bool cmp(straight x, straight y){ if(x.a != y.a) return x.a < y.a; return x.b < y.b; } int main(){ int T, n; cin >> T; while(T--){ cin >> n; for(int i = 0; i < n; i++) cin >> Lu[i].a >> Lu[i].b; sort(Lu, Lu + n, cmp); int cot = 0; for(int i = 0; i < n - 1; i++) { if(Lu[i].a == Lu[i + 1].a) continue; Lu[cot++] = Lu[i]; } Lu[cot++] = Lu[n - 1]; if(cot < 2){ cout << cot << endl; continue; } double x = (Lu[1].b - Lu[0].b)*1.0/(Lu[0].a - Lu[1].a); double y; int sum = 2; Hui[1] = Lu[1]; Hui[0] = Lu[0]; for(int i = 2; i < cot; i++){ y = (Lu[i].b - Hui[sum - 1].b)*1.0/(Hui[sum - 1].a - Lu[i].a);//求当前线与前一条线的交点 while(y <= x){//如果交点比前一条线的交点靠前，那么前一条线被遮住，一下循环重复比较过程 sum--; if(sum > 1){ x = (Hui[sum - 1].b - Hui[sum - 2].b)*1.0/(Hui[sum - 2].a - Hui[sum - 1].a); y = (Lu[i].b - Hui[sum - 1].b)*1.0/(Hui[sum - 1].a - Lu[i].a); } else{ y = (Lu[i].b - Hui[sum - 1].b)*1.0/(Hui[sum - 1].a - Lu[i].a); break; } } Hui[sum++] = Lu[i]; x = y; } cout << sum << endl; } return 0; }