Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Problem: B. Forest protection
- // Contest: Codeforces - 2018 Southern Russia Open Championship – XII SFU Olympiad «ContestSFedU-2018». Team Final.
- // URL: https://codeforces.com/group/j7YsoIFtw4/contest/101790/problem/B
- // Memory Limit: 256 MB
- // Time Limit: 2000 ms
- #include <bits/stdc++.h>
- using namespace std;
- template<typename T>ostream&operator<<(ostream&out,const vector<T>&vec){if(vec.empty()){out<<"[]";return out;}out<<'[';for(int i=0;i<(int)vec.size()-1;i++){out<<vec[i]<<", ";}return out<<vec.back()<<']';}
- template<typename T>ostream&operator<<(ostream&out,const set<T>&set){out<<'{';for(auto it=set.begin();it!=set.end();it++){T element=*it;out<<element;if(next(it)!=set.end()){out<<", ";}}return out<<'}';}
- template<typename T>ostream&operator<<(ostream&out,const unordered_set<T>&set){out<<'{';for(auto it=set.begin();it!=set.end();it++){T element=*it;out<<element;if(next(it)!=set.end()){out<<", ";}}return out<<'}';}
- template<typename T>ostream&operator<<(ostream&out,const multiset<T>&set){out<<'{';for(auto it=set.begin();it!=set.end();it++){T element=*it;out<<element;if(next(it)!=set.end()){out<<", ";}}return out<<'}';}
- template<typename T>ostream&operator<<(ostream&out,const unordered_multiset<T>&set){out<<'{';for(auto it=set.begin();it!=set.end();it++){T element=*it;out<<element;if(next(it)!=set.end()){out<<", ";}}return out<<'}';}
- template<typename T1,typename T2>ostream&operator<<(ostream&out,const pair<T1,T2>&pair){return out<<'('<<pair.first<<", "<<pair.second<<')';}
- typedef long long ll;
- typedef long double ld;
- typedef vector<int> vi;
- typedef vector<vector<int>> vvi;
- typedef vector<ll> vl;
- typedef vector<vector<ll>> vvl;
- #define pb push_back
- #define endl "\n"
- #define rep(i, a, b) for(int i = a; i < (b); ++i)
- #define all(x) begin(x), end(x)
- #define sz(x) (int)(x).size()
- typedef long long ll;
- typedef pair<int, int> pii;
- typedef vector<int> vi;
- template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
- template<class T>
- struct Point {
- typedef Point P;
- T x, y;
- explicit Point(T x=0, T y=0) : x(x), y(y) {}
- bool operator<(P p) const { return tie(x,y) < tie(p.x,p.y); }
- bool operator==(P p) const { return tie(x,y)==tie(p.x,p.y); }
- P operator+(P p) const { return P(x+p.x, y+p.y); }
- P operator-(P p) const { return P(x-p.x, y-p.y); }
- P operator*(T d) const { return P(x*d, y*d); }
- P operator/(T d) const { return P(x/d, y/d); }
- T dot(P p) const { return x*p.x + y*p.y; }
- T cross(P p) const { return x*p.y - y*p.x; }
- T cross(P a, P b) const { return (a-*this).cross(b-*this); }
- T dist2() const { return x*x + y*y; }
- double dist() const { return sqrt((double)dist2()); }
- // angle to x−axis in interva l [−pi , pi ]
- double angle() const { return atan2(y, x); }
- P unit() const { return *this/dist(); } // makes d is t ()=1
- P perp() const { return P(-y, x); } // rotates +90 degrees
- P normal() const { return perp().unit(); }
- // returns point rotated ’a ’ radians ccw around the origin
- P rotate(double a) const {
- return P(x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)); }
- friend ostream& operator<<(ostream& os, P p) {
- return os << "(" << p.x << "," << p.y << ")"; }
- };
- typedef Point<ll> P;
- vector<P> convexHull(vector<P> pts) {
- if (sz(pts) <= 1) return pts;
- sort(all(pts));
- vector<P> h(sz(pts)+1);
- int s = 0, t = 0;
- for (int it = 2; it--; s = --t, reverse(all(pts)))
- for (P p : pts) {
- while (t >= s + 2 && h[t-2].cross(h[t-1], p) <= 0) t--;
- h[t++] = p;
- }
- return {h.begin(), h.begin() + t - (t == 2 && h[0] == h[1])};
- }
- array<P, 2> hullDiameter(vector<P> S) {
- int n = sz(S), j = n < 2 ? 0 : 1;
- pair<ll, array<P, 2>> res({0, {S[0], S[0]}});
- rep(i,0,j)
- for (;; j = (j + 1) % n) {
- res = max(res, {(S[i] - S[j]).dist2(), {S[i], S[j]}});
- if ((S[(j + 1) % n] - S[j]).cross(S[i + 1] - S[i]) >= 0)
- break;
- }
- return res.second;
- }
- struct pt {
- ll x, y;
- pt(ll x=0, ll y=0) : x(x), y(y) {}
- };
- int orientation(pt a, pt b, pt c) {
- double v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
- if (v < 0) return -1; // clockwise
- if (v > 0) return +1; // counter-clockwise
- return 0;
- }
- bool cw(pt a, pt b, pt c, bool include_collinear) {
- int o = orientation(a, b, c);
- return o < 0 || (include_collinear && o == 0);
- }
- bool ccw(pt a, pt b, pt c, bool include_collinear) {
- int o = orientation(a, b, c);
- return o > 0 || (include_collinear && o == 0);
- }
- void convex_hull(vector<pt>& a, bool include_collinear = false) {
- if (a.size() == 1)
- return;
- sort(a.begin(), a.end(), [](pt a, pt b) {
- return make_pair(a.x, a.y) < make_pair(b.x, b.y);
- });
- pt p1 = a[0], p2 = a.back();
- vector<pt> up, down;
- up.push_back(p1);
- down.push_back(p1);
- for (int i = 1; i < (int)a.size(); i++) {
- if (i == a.size() - 1 || cw(p1, a[i], p2, include_collinear)) {
- while (up.size() >= 2 && !cw(up[up.size()-2], up[up.size()-1], a[i], include_collinear))
- up.pop_back();
- up.push_back(a[i]);
- }
- if (i == a.size() - 1 || ccw(p1, a[i], p2, include_collinear)) {
- while (down.size() >= 2 && !ccw(down[down.size()-2], down[down.size()-1], a[i], include_collinear))
- down.pop_back();
- down.push_back(a[i]);
- }
- }
- if (include_collinear && up.size() == a.size()) {
- reverse(a.begin(), a.end());
- return;
- }
- a.clear();
- for (int i = 0; i < (int)up.size(); i++)
- a.push_back(up[i]);
- for (int i = down.size() - 2; i > 0; i--)
- a.push_back(down[i]);
- }
- ll ori(Point<ll> a, Point<ll>b, Point<ll>c) {
- ll v = a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y);
- if (v < 0) return -1; // clockwise
- if (v > 0) return +1; // counter-clockwise
- return 0;
- }
- void solve() {
- ll n;
- cin >> n;
- vector<Point<ll>> pts(n);
- vector<pt> pts2(n);
- for(int i = 0; i < n; i++) {
- ll x,y;
- cin >> x >> y;
- pts[i] = Point<ll>(x,y);
- pts2[i] = pt(x,y);
- }
- bool suc = false;
- for(int i = 1; i < n; i++) {
- if (ori(pts[i], pts[i-1], pts[0]) == 0) {
- continue;
- } else {
- suc = true;
- break;
- }
- }
- if(!suc) {
- cout << n << endl;
- return;
- }
- // cout << pts << endl;
- vector<Point<ll>> hull2 = convexHull(pts);
- if ((int) hull2.size() == 3) {
- cout << 2 << endl;
- return;
- }
- convex_hull(pts2, true);
- vector<pt> hull_col = pts2;
- vector<Point<ll>> hull (hull_col.size());
- for(int i = 0; i < (int) hull_col.size(); i++) {
- hull[i] = Point<ll>(hull_col[i].x, hull_col[i].y);
- }
- // cout << hull << endl;
- array<P, 2> diam = hullDiameter(hull2);
- // cout << diam[0] << " " << diam[1] << endl;
- Point<ll> p1 = diam[0];
- Point<ll> p2 = diam[1];
- int ind1 = -1;
- int ind2 = -1;
- for(int i = 0; i < (int) hull.size(); i++) {
- if(hull[i] == p1) {
- ind1 = i;
- } else if(hull[i] == p2) {
- ind2 = i;
- }
- }
- int hind1 = -1;
- int hind2 = -1;
- for(int i = 0; i < (int) hull2.size(); i++) {
- if(hull2[i] == p1) {
- hind1 = i;
- } else if(hull2[i] == p2) {
- hind2 = i;
- }
- }
- // cout << p1 << " " << p2 << endl;
- //
- // cout << hull << endl;
- // cout << hull2 << endl;
- // cout << ind1 << " " << ind2 << endl;
- // cout << hind1 << " " << hind2 << endl;
- ll dist = max(ind1, ind2) - min(ind1, ind2) + 1;
- ll other_dist = hull.size() - dist + 2;
- ll sol = min(dist, other_dist);
- // cout << dist << " " << other_dist << endl;
- // collinear edges
- // if((min(hind1,hind2) + 1 == max(hind1,hind2)) || (min(hind1,hind2) == 0 && max(hind1,hind2) == (int) hull2.size()) {
- //
- // }
- // cout << hull << endl;
- //
- // cout << dist << " " << other_dist << endl;
- cout << sol << endl;
- // ll ans = max(ind1,ind2) - min(ind2,ind1);
- }
- int main() {
- ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cout.precision(20);
- int tc = 1;
- // cin >> tc;
- for (int t = 1; t <= tc; t++) {
- solve();
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment