比赛 USACO银组重赛hhh 评测结果 AAAAAAAAAA
题目名称 Triangles(Silver) 最终得分 100
用户昵称 数声风笛ovo 运行时间 0.629 s
代码语言 C++ 内存使用 16.41 MiB
提交时间 2020-03-01 19:44:50
显示代码纯文本
//非本人代码,测试官方数据用 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define f first
#define s second

const int MOD = 1e9+7; 

void setIO(string s) {
  ios_base::sync_with_stdio(0); cin.tie(0); 
  freopen((s+".in").c_str(),"r",stdin);
  freopen((s+".out").c_str(),"w",stdout);
}

struct mi {
  int v; explicit operator int() const { return v; }
  mi(ll _v) : v(_v%MOD) { v += (v<0)*MOD; }
  mi() : mi(0) {}
};
mi operator+(mi a, mi b) { return mi(a.v+b.v); }
mi operator-(mi a, mi b) { return mi(a.v-b.v); }
mi operator*(mi a, mi b) { return mi((ll)a.v*b.v); }
 
int N;
vector<pair<int,int> > v;
vector<mi> sum[100005];
vector<pair<int,int> > todo[20001];
 
void check() {
	for (int i = 0; i <= 20000; ++i) if (todo[i].size() > 0) {
		int sz = todo[i].size();
		sort(todo[i].begin(),todo[i].end());
		mi cur = 0; 
		for (int j = 0; j < sz; ++j) 
			cur = cur+todo[i][j].f-todo[i][0].f;
		for (int j = 0; j < sz; ++j) {
			if (j) cur = cur+(2*j-sz)*(todo[i][j].f-todo[i][j-1].f);
			sum[todo[i][j].s].push_back(cur);
		}
	}
}
 
int main() {
	setIO("usaco_Feb_triangles"); 
	cin >> N; v.resize(N); 
	for (int i = 0; i < N; ++i) cin >> v[i].f >> v[i].s;
	for (int i = 0; i <= 20000; ++i) todo[i].clear();
	for (int i = 0; i < N; ++i) 
		todo[v[i].f+10000].push_back({v[i].s,i});
	check();
	for (int i = 0; i <= 20000; ++i) todo[i].clear();
	for (int i = 0; i < N; ++i) 
		todo[v[i].s+10000].push_back({v[i].f,i});
	check();
	mi ans = 0; 
	for (int i = 0; i < N; ++i) ans = ans+sum[i][0]*sum[i][1];
	cout << ans.v << "\n";
}