忽然觉得这个题很有必要写题解。

移项

y-x^2 = bx+c

那么其实就是找有多少条直线上方没有点

所以就是一个上凸壳有多少条直线/点.

绝妙啊!!!!

太妙了啊!!!!

神乎其技卧槽!!!

(我是傻逼)

 #include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
typedef long long db;
const double eps=1e-;
const double pi=acos(-);
int sign(db k){
if (k>eps) return ; else if (k<-eps) return -; return ;
}
int cmp(db k1,db k2){return sign(k1-k2);}
struct point{
db x,y;
point operator + (const point &k1) const{return (point){k1.x+x,k1.y+y};}
point operator - (const point &k1) const{return (point){x-k1.x,y-k1.y};}
point operator * (db k1) const{return (point){x*k1,y*k1};}
point operator / (db k1) const{return (point){x/k1,y/k1};}
bool operator == (const point &k1) const{return cmp(x,k1.x)==&&cmp(y,k1.y)==;}
bool operator <(const point &k1)const {
int c=cmp(x,k1.x);
if(c)return c==-;
return cmp(y,k1.y)==-;
}
};
db cross(point k1,point k2){return k1.x*k2.y-k1.y*k2.x;}
db dot(point k1,point k2){return k1.x*k2.x+k1.y*k2.y;}
int n;
vector<point> convexHull(vector<point> ps){
int n = ps.size();if(n<=)return ps;
sort(ps.begin(),ps.end());
vector<point> qs(n*);int k=;
for(int i=;i<n;qs[k++]=ps[i++])
while (k>&&cross(qs[k-]-qs[k-],ps[i]-qs[k-])<=)--k;
for(int i=n-,t=k;i>=;qs[k++]=ps[i--])
while (k>t&&cross(qs[k-]-qs[k-],ps[i]-qs[k-])<=)--k;
qs.resize(k-);
return qs;
}
void getUDP(vector<point>A,vector<point>&U,vector<point>&D){
db l=1e7,r=-1e7;
for (int i=;i<A.size();i++) l=min(l,A[i].x),r=max(r,A[i].x);
int wherel,wherer;
for (int i=;i<A.size();i++) if (cmp(A[i].x,l)==) wherel=i;
for (int i=A.size();i;i--) if (cmp(A[i-].x,r)==) wherer=i-;
U.clear(); D.clear(); int now=wherel;
while (){D.push_back(A[now]); if (now==wherer) break; now++; if (now>=A.size()) now=;}
now=wherel;
while (){U.push_back(A[now]); if (now==wherer) break; now--; if (now<) now=A.size()-;}
}
vector<point>p,u,d;
db x,y;
int main(){
scanf("%d",&n);
db mx=;
for(int i=;i<=n;i++){
scanf("%lld%lld",&x,&y);
p.push_back(point{x,y-x*x});
mx+=x;
}
p=convexHull(p);
getUDP(p,u,d);
set<int>s;
for(auto p:u)s.insert(p.x);
printf("%d\n",s.size()-);
}

最新文章

  1. 《ES6基础教程》之 map、forEach、filter indexOf 用法
  2. Vue - 实例
  3. net MVC 重定向总结
  4. iptables4张表5条链
  5. eclipse为方法添加注释的快捷键是什么
  6. Windows Azure Cloud Service (44) 将Cloud Service加入Virtual Network Subnet,并固定Virtual IP Address(VIP)
  7. c++学习-字符串
  8. 树&amp;二叉树&amp;二叉搜索树
  9. 【转】SourceTree的简单使用
  10. Centos common software install
  11. Java中Iterator(迭代器)的用法及其背后机制的探究
  12. Delphi5的System.pas只有11514行
  13. php 随笔
  14. angular element()
  15. 2015阿里巴巴安全峰会PPT
  16. NewsDaoImpl
  17. java课程设计(Calculator) 201521123027 陈龙
  18. sublime text3 开发必备插件
  19. NodeJS学习笔记(二)
  20. Delphi IdHTTP1下载文件防止假死 (

热门文章

  1. 2018-2019-2 20165234 《网络对抗技术》 Exp3 免杀原理与实践
  2. Linux查看日志工具
  3. JSR-303 数据校验学习
  4. webpack2 实践
  5. springboo+nginx测试反向代理01
  6. iframe 加form提交数据
  7. SpringBoot相关错误
  8. 快捷键打开Generate
  9. 洛谷 P3366 【模板】最小生成树
  10. Jmeter4.0+版本If Controller使用