#include<iostream>
#include<vector>
#include<set>
#include<cmath>
#include<map>
#define ll long long
#define pi pair < ll,ll >
#define mp(a,b) make_pair(a,b)
#define rep(i,a,b) for(int i = a;i < b;i++)
#define MAXN 200000
using namespace std;
ll n,mod=1000000000;
pi ar[MAXN];
map < pi,bool > grid;
ll dx[] = {-1,1,0,0};
ll dy[] = {0,0,1,-1};
pi xcords;
pi ycords;
map < pi,bool > vis;
void dfs(pi cur)
{
vis[cur]=true;
xcords.first = min(xcords.first,cur.first);
ycords.first = min(ycords.first,cur.second);
xcords.second = max(xcords.second,cur.first);
ycords.second = max(ycords.second,cur.second);
rep(d,0,4)
{
pi neo = cur;
neo.first+=dx[d];
neo.second+=dy[d];
if(!vis[neo] && grid[neo])
{
dfs(neo);
}
}
return;
}
ll expo(ll v,ll e)
{
if(e == 0)
return 1;
if(e == 1)
return v;
ll x = expo(v,e/2);
x =(x*x)%mod;
if(e%2==1)
x=(x*v)%mod;
return x;
}
ll inverse(ll x)
{
return expo(x,mod-2);
}
ll calculate_sum()
{
ll w = xcords.second-xcords.first+1;
ll h = ycords.second-ycords.first+1;
ll res = ((((((w-1)*w)%mod)*((h*h)%mod))%mod*(w+1))%mod + (((((h-1)*h)%mod)*((w*w)%mod))%mod*(h+1))%mod)*inverse(6)%mod;
}
//int DistanceSum(int N, int *X, int *Y)
int main()
{
cin >> n;
// n=N;
rep(i,0,n)
{/*
ar[i].first =X[i];
ar[i].second=Y[i];
*/
cin >> ar[i].first>>ar[i].second;
grid[mp(ar[i].first,ar[i].second)] = true;
}
xcords.first = ar[0].first;
xcords.second = ar[0].first;
ycords.first = ar[0].second;
ycords.second = ar[0].second;
dfs(ar[0]);
cout<<calculate_sum();
}
/*
6
0 0
0 1
0 2
1 2
1 1
1 0
*/
Compilation message
city.cpp: In function 'long long int calculate_sum()':
city.cpp:73:8: warning: unused variable 'res' [-Wunused-variable]
ll res = ((((((w-1)*w)%mod)*((h*h)%mod))%mod*(w+1))%mod + (((((h-1)*h)%mod)*((w*w)%mod))%mod*(h+1))%mod)*inverse(6)%mod;
^~~
city.cpp:74:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
/tmp/ccYAbsRx.o: In function `main':
city.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccYmw9Aj.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccYmw9Aj.o: In function `main':
grader.cpp:(.text.startup+0xf1): undefined reference to `DistanceSum(int, int*, int*)'
collect2: error: ld returned 1 exit status
