CF1142C U2

$y>x^2+bx+c$也就是$y-x^2>bx+c$

左边是点，右边是直线.

维护上凸包.

虽然这么简单但就是做不出来。

 1 #include<cstdio>
 2 #include<algorithm>
 3 #define Rint register int
 4 using namespace std;
 5 typedef long long LL;
 6 const int N = 100003;
 7 struct Point {
 8     LL x, y;
 9     inline Point(LL _x = 0, LL _y = 0): x(_x), y(_y){}
10     inline Point operator - (const Point &o) const {return Point(x - o.x, y - o.y);}
11     inline LL operator * (const Point &o) const {return x * o.y - y * o.x;}
12     inline bool operator < (const Point &o) const {return x < o.x || x == o.x && y > o.y;}
13 } p[N], q[N], stk[N];
14 int n, m, top;
15 int main(){
16     scanf("%d", &n);
17     for(Rint i = 1;i <= n;i ++){
18         scanf("%I64d %I64d", &p[i].x, &p[i].y);
19         p[i].y -= p[i].x * p[i].x;
20     }
21     sort(p + 1, p + n + 1);
22     q[m = 1] = p[1];
23     for(Rint i = 2;i <= n;i ++) if(p[i].x != p[i - 1].x) q[++ m] = p[i];
24     for(Rint i = 1;i <= m;i ++){
25         while(top > 1 && (stk[top] - stk[top - 1]) * (q[i] - stk[top - 1]) >= 0) -- top;
26         stk[++ top] = q[i];
27     }
28     printf("%d
", top - 1);
29 } // nantf tai qiang le!

CF1142C