Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #pragma GCC optimize("Ofast")
- //#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
- #include <bits/stdc++.h>
- #define ll long long
- #define ld long double
- #define F first
- #define S second
- #define pb push_back
- using namespace std;
- mt19937_64 gen(time(0));
- const int maxn = 1e5 + 5;
- const int maxa = 1e4 + 5;
- const ll mod = 1e9 + 7;
- pair <int, int> a[maxn];
- map <int, vector <pair <int, ll>>> r;
- map <int, vector <pair <int, ll>>> c;
- map <int, vector <pair <int, ll>>> rr;
- map <int, vector <pair <int, ll>>> cc;
- int main()
- {
- #ifdef LOCAL
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #else
- freopen("triangles.in", "r", stdin);
- freopen("triangles.out", "w", stdout);
- #endif
- int n;
- cin >> n;
- for(int i = 0; i < n; ++i)
- {
- cin >> a[i].F >> a[i].S;
- r[a[i].F].pb({a[i].S, 0});
- rr[a[i].F].pb({a[i].S, 0});
- c[a[i].S].pb({a[i].F, 0});
- cc[a[i].S].pb({a[i].F, 0});
- }
- for(auto& pp : r)
- {
- sort(pp.S.begin(), pp.S.end());
- ll sum = 0;
- ll cnt = 0;
- for(int i = int(pp.S.size()) - 2; i >= 0; --i)
- {
- ++cnt;
- sum *= 2;
- sum += (pp.S[i + 1].F - pp.S[i].F) * cnt;
- sum %= mod;
- pp.S[i].S = sum;
- }
- }
- for(auto& pp : rr)
- {
- sort(pp.S.begin(), pp.S.end());
- ll sum = 0;
- ll cnt = 0;
- for(int i = 1; i < int(pp.S.size()); ++i)
- {
- ++cnt;
- sum *= 2;
- sum += (pp.S[i].F - pp.S[i - 1].F) * cnt;
- sum %= mod;
- pp.S[i].S = sum;
- }
- }
- for(auto& pp : c)
- {
- sort(pp.S.begin(), pp.S.end());
- ll sum = 0;
- ll cnt = 0;
- for(int i = int(pp.S.size()) - 2; i >= 0; --i)
- {
- ++cnt;
- sum *= 2;
- sum += (pp.S[i + 1].F - pp.S[i].F) * cnt;
- sum %= mod;
- pp.S[i].S = sum;
- }
- }
- for(auto& pp : cc)
- {
- sort(pp.S.begin(), pp.S.end());
- ll sum = 0;
- ll cnt = 0;
- for(int i = 1; i < int(pp.S.size()); ++i)
- {
- ++cnt;
- sum *= 2;
- sum += (pp.S[i].F - pp.S[i - 1].F) * cnt;
- sum %= mod;
- pp.S[i].S = sum;
- }
- }
- ll ans = 0;
- for(int i = 0; i < n; ++i)
- {
- ll fir1 = (*lower_bound(r[a[i].F].begin(), r[a[i].F].end(), make_pair(a[i].S, -1ll))).S;
- ll fir2 = (*lower_bound(rr[a[i].F].begin(), rr[a[i].F].end(), make_pair(a[i].S, -1ll))).S;
- ll sec1 = (*lower_bound(c[a[i].S].begin(), c[a[i].S].end(), make_pair(a[i].F, -1ll))).S;
- ll sec2 = (*lower_bound(cc[a[i].S].begin(), cc[a[i].S].end(), make_pair(a[i].F, -1ll))).S;
- // cerr << i << ' ' << fir << ' ' << sec << endl;
- ans += fir1 * sec1 + fir1 * sec2 + fir2 * sec1 + fir2 * sec2;
- ans %= mod;
- }
- cout << ans;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement