zoj 2967 Colorful Rainbows

zoj 2967 Colorful Rainbows

#include <cstdio>#include <cstring>#include <cstdlib>#include <cmath>#include <queue>#include <stack>#include <vector>#include <string>#include <set>#include <map>#include <algorithm>using namespace std;const double eps = 1e-8;int sgn(double a) { return a < -eps ? -1 : a < eps ? 0 : 1;}struct HalfPlane { double k, b; bool operator == (const HalfPlane & hb) const { return k - hb.k == 0; } bool operator < (const HalfPlane & hb) const { if ((*this) == hb) { return b - hb.b > 0; } else { return k - hb.k < 0; } }};double get_insect(HalfPlane h1, HalfPlane h2) { return (h2.b - h1.b) / (h1.k - h2.k);}int main(void) { int t; scanf("%d", &t); for (int cases = 1; cases <= t; cases++) { int n; scanf("%d", &n); vector<HalfPlane> hp; hp.resize(n); for (int i = 0 ; i < n; i++) { scanf("%lf%lf", &hp[i].k, &hp[i].b); } sort(hp.begin(), hp.end()); n = unique(hp.begin(), hp.end()) - hp.begin(); hp.resize(n); vector<HalfPlane> stk; for (int i = 0; i < n; i++) { if (i == 0) { stk.push_back(hp[i]); } else { while (stk.size() > 1 && get_insect(hp[i], stk[stk.size() - 1]) <= get_insect(stk[stk.size() - 1], stk[stk.size() - 2])) { stk.erase(stk.begin() + stk.size() - 1); } stk.push_back(hp[i]); } } printf("%dn", stk.size()); } return 0;}