# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
166986 | Charis02 | Ideal city (IOI12_city) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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
*/