可以变换坐标:x' = x, y' = y - x ^ 2,如此之后可得线性函数x' * b + c = y',可以发现两点连边为抛物线,而其他点都在这条线下方才满足题意,故而求一个上凸壳即可。

 #include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std; typedef long long ll;
const int maxn = 1e5 + ;
int n;
struct Point {
ll x, y; Point(){}
Point(ll x, ll y):x(x), y(y) {} friend ll operator * (const Point &a, const Point &b) {
return a.y * b.x - b.y * a.x;
} friend Point operator - (const Point &a, const Point &b) {
return Point(a.x - b.x, a.y - b.y);
} bool operator < (const Point &rhs) const {
if (x != rhs.x) return x < rhs.x;
return y < rhs.y;
}
}; vector<Point> v, st; void read() {
cin >> n; for (int i = ; i < n; i++) {
ll x, y;
cin >> x >> y;
y = y - x * x;
v.push_back({x, y});
}
} void convex() {
sort(v.begin(), v.end());//按坐标排序 for (int i = n - ; ~i; --i)
v[i] = v[i] - v[]; for (int i = ; i < n; i++) {
int tot = st.size();
while (tot > && (v[i] - st[tot - ]) * (st[tot - ] - st[tot - ]) >= ) tot--, st.pop_back();
st.push_back(v[i]);
}
} int main() {
ios_base::sync_with_stdio();
cin.tie(), cout.tie(); read();
convex(); int ans = ;
for (int i = ; i < st.size(); i++)
if (st[i].x != st[i - ].x)//x相同无法构成二次函数
ans++;
cout << ans << endl; return ;
}

最新文章

  1. 家族/亲戚(relation)
  2. 墨菲定律-Murphy&#39;s Law (转载)
  3. NABC模型进行需求分析
  4. ActiveMQ 使用
  5. IntelliJ IDEA集成svn
  6. 『转载』Debussy快速上手(Verdi相似)
  7. EF 6 调用存储过程时返回多结果集和OUTPUT参数问题
  8. 是男人就下100层【第四层】——Crazy贪吃蛇(1)
  9. Mybatis框架 基础
  10. Kubernetes入门-集群安装
  11. python-文件锁
  12. qt quick-初始学习概念
  13. java多线程快速入门(八)
  14. confluence5.65+CentOS+mysql安装破解
  15. Android加密解密
  16. 利用oneproxy实现mysql读写分离搭建笔记
  17. LeetCode-13. Roman to Integer(罗马数字转阿拉伯数字)
  18. Redis--初入
  19. awrsqrpt.sql简介
  20. 设计模式——原型模式(Prototype Pattern)

热门文章

  1. 第一个自定义开发的Arcgis地图
  2. webform中实现SQL Sever2008数据库数据分页查询
  3. 旋转屏幕导致Activity重建
  4. codeforces B. Coach 解题报告
  5. 常规问题解决:File &quot;/usr/bin/yum&quot;, line 30 及 File &quot;/usr/libexec/urlgrabber-ext-down&quot;, line 28
  6. Myeclipse项目内容没有报错但是项目上面却有红色叉叉
  7. 安装asterisk以及asterisk-gui
  8. webpack 基本功能和原理
  9. SQLite win7
  10. OS__信号量(semaphore)PV操作