Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- using namespace std;
- #include <vector>
- #include <queue>
- #include <algorithm>
- #include <cmath>
- #include <utility>
- #include <bitset>
- #include <set>
- #include <string>
- #include <iomanip>
- #include <map>
- #define pb push_back
- #define pii pair<int,int>
- #define F first
- #define S second
- #define LL long long
- #define mid (LB+RB)/2
- #define iter(x) x.begin(),x.end()
- /*
- 8e7 so dian
- FHVirus so dian
- youou so dian
- KYW so dian
- hubert so dian
- jass so dian
- tingyu so dian
- */
- //IO
- #include <iostream>
- #define theyRSOOOOOOOOODIAN ios_base::sync_with_stdio(false),cin.tie(0);
- #define endl '\n'
- //workspace
- #define x first
- #define y second
- inline bool cross(pii o,pii a,pii b){
- return (a.x - o.x) * (b.y - o.y) <= (a.y - o.y) * (b.x - o.x);
- }
- struct stack{
- pii data[100100];
- int p = 0;
- inline void push(pii x){
- data[p++] = x;
- }
- inline pii top(){
- return data[p-1];
- }
- inline pii sectop(){
- return data[p-2];
- }
- inline bool pop(){
- if (p){
- --p;
- return 1;
- }
- return 0;
- }
- inline int unsigned size(){
- return p;
- }
- };
- int main(){
- theyRSOOOOOOOOODIAN
- int n;
- vector <pii> v;
- cin >> n;
- while (n--){
- int X,Y;
- cin >> X >> Y;
- v.pb({X,Y});
- }
- sort (iter(v));
- stack ch;
- for (auto i:v){
- while (ch.size() >= 2 && cross(ch.sectop(),ch.top(),i))
- ch.pop();
- ch.push(i);
- }
- for (int i=v.size()-2,lm=ch.size()+1;i>=0;--i){
- while (ch.size() >= lm && cross(ch.sectop(),ch.top(),v[i]))
- ch.pop();
- if (i)
- ch.push(v[i]);
- }
- cout << ch.size();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement