Submission #59499776

---

Source Code Expand

#include<bits/stdc++.h>
#include"atcoder/all"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(a) a.begin(),a.end()
typedef long long ll;
typedef vector<ll> vi;
constexpr ll mod = 998244353;
typedef modint998244353 mi;

ll x[100005],y[100005];
typedef pair<ll,ll> P;

P operator- (const P &lhs,const P &rhs) {
    return {rhs.first-lhs.first,rhs.second-lhs.second};
}

ll det(P x,P y){
    return x.first*y.second-x.second*y.first;   
}

vector<P> convex_hull(vector<P>&ps,int n){
    sort(ps.begin(),ps.end());
    int k=0;
    vector<P>qs(2*n);

	rep(i, n){
		while(k>1&&det(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<=0)k--;
		qs[k++]=ps[i];
	}
	for (int i=n-2,t=k;i>=0;i--){
		while(k>t&&det(qs[k-1]-qs[k-2],ps[i]-qs[k-1])<=0)k--;
		qs[k++]=ps[i];
	}
	qs.resize(k - 1);
	return qs;
}

ll my_floor_sum(ll n,ll m,ll a,ll b){
    ll ans=0;
    ans+=n*(b/m);
    b%=m;

    ll ma=(a%m+m)%m;
    ll dv=(a-ma)/m;
    ans+=dv*(n-1)*n/2;
    ans+=floor_sum(n,m,ma,b);
    return ans;
}

int main(){
    int n;cin>>n;
    rep(i,n)cin>>x[i]>>y[i];

    vector<P>ps(n);
    rep(i,n)ps[i]={x[i],y[i]};

    vector<P>ch=convex_hull(ps,n);
    int ch_size=ch.size();
    ch.push_back(ch[0]);

    ll ans=0;
    rep(i,ch_size){
        if(ch[i]<ch[i+1]){
            ll m=ch[i+1].first-ch[i].first;
            if(m==0){
                continue;
            }
            else{
                ll a=ch[i+1].second-ch[i].second;
                ll b=m*ch[i].second-1;
                ans-=my_floor_sum(m,m,a,b);
            }
        }
        else{
            ll m=ch[i].first-ch[i+1].first;
            if(m==0){
                continue;
            }
            else{
                ll a=ch[i+1].second-ch[i].second;
                ll b=m*ch[i].second;
                ans+=my_floor_sum(m,m,a,b);
            }
        }
    }

    ll x_min=1e18,x_max=-1e18;
    ll y_min=-1,y_max=1e9;

    rep(i,n){
        x_min=min(x_min,x[i]);
        x_max=max(x_max,x[i]);
    }
    rep(i,n){
        if(x[i]==x_min)y_min=max(y_min,y[i]);
        if(x[i]==x_max)y_max=min(y_max,y[i]-1);
    }
    ans+=y_min-y_max;
    cout<<ans-n<<endl;
}

Submission Info

Judge Result