Home » 国际竞赛 » Details

USACO 2020 February Contest, Silver Problem 2. Triangles

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日上午11:58

Farmer John would like to create a triangular pasture for his cows.

There are $N$ fence posts ( $3 \leq N \leq 10^{5}$ ) at distinct points $(X_{1}, Y_{1}) \dots (X_{N}, Y_{N})$ on the 2D map of his farm. He can choose three of them to form the vertices of the triangular pasture as long as one of the sides of the triangle is parallel to the $x$ -axis and another side is parallel to the $y$ -axis.

What is the sum of the areas of all possible pastures that FJ can form?

SCORING:

Test case 2 satisfies $N = 200.$
Test cases 3-4 satisfy $N \leq 5000.$
Test cases 5-10 satisfy no additional constraints.

INPUT FORMAT (file triangles.in):

The first line contains $N .$ Each of the next $N$ lines contains two integers $X_{i}$ and $Y_{i}$ , each in the range $- 10^{4} \dots 10^{4}$ inclusive, describing the location of a fence post.

OUTPUT FORMAT (file triangles.out):

As the sum of areas is not necessarily be an integer and may be very large, output the remainder when two times the sum of areas is taken modulo $10^{9} + 7$ .

SAMPLE INPUT:

SAMPLE OUTPUT:

Fence posts $(0, 0)$ , $(1, 0)$ , and $(1, 2)$ give a triangle of area $1$ , while $(0, 0)$ , $(1, 0)$ , and $(0, 1)$ give a triangle of area $0.5$ . Thus, the answer is $2 \cdot (1 + 0.5) = 3.$

Problem credits: Travis Hance and Nick Wu

USACO 2020 February Contest, Silver Problem 2. Triangles 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Suppose that we want to find two times the sum of areas of all triangles with right angle at $(X_{1}, Y_{1})$ . Let $A_{1} = {Y_{i} | X_{i} = X_{1}}$ (the set of $Y$ -coordinates for all points that share the same $X$ -coordinate as post $1$ ) and $B_{1} = {X_{j} | Y_{j} = Y_{1}}$ . Then the desired quantity will equal

(\sum y \in A | Y 1 - y |) \cdot (\sum x \in B | X 1 - x |) .

It remains to compute the value of $\sum_{x \in B_{i}} | X_{i} - x |$ for every $i$ . The summation involving $y$ can be computed similarly.

What we need to do, restated more simply:

For integers $x_{1} \leq x_{2} \leq \dots \leq x_{n}$ , compute $s_{i} = \sum_{j = 1}^{n} | x_{i} - x_{j} |$ for each $i$ .

This can be done in linear time. First, compute $s_{1}$ . Then for all $1 \leq i < N$ , $s_{i + 1} = s_{i} + (2 i - N) (x_{i + 1} - x_{i}) .$

Overall, the solution runs in $O (N \log N)$ time because we first need to sort the $x$ -coordinates for each $y$ .

#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(begin(todo[i]),end(todo[i]));
		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("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";
}

[/hide]