USACO 2020 February Contest, Silver Problem 2. Triangles

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

There are?NN?fence posts (3≤N≤1053≤N≤105) at distinct points?(X1,Y1)…(XN,YN)(X1,Y1)…(XN,YN)?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?xx-axis and another side is parallel to the?yy-axis.

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

 

 

 

 

SAMPLE INPUT:

4
0 0
0 1
1 0
1 2

SAMPLE OUTPUT:

3

Fence posts?(0,0)(0,0),?(1,0)(1,0), and?(1,2)(1,2)?give a triangle of area?11, while?(0,0)(0,0),?(1,0)(1,0), and?(0,1)(0,1)?give a triangle of area?0.50.5. Thus, the answer is?2?(1+0.5)=3.2?(1+0.5)=3.

 

Problem credits: Travis Hance and Nick Wu

USACO 2020 February Contest, Silver Problem 2. Triangles 題解(翰林國(guó)際教育提供，僅供參考)

題解請(qǐng)注冊(cè)或登錄查看

[/hide]

(Analysis by Benjamin Qi)

Suppose that we want to find two times the sum of areas of all triangles with right angle at?(X1,Y1)(X1,Y1). Let?A1={Yi|Xi=X1}A1={Yi|Xi=X1}?(the set of?YY-coordinates for all points that share the same?XX-coordinate as post?11) and?B1={Xj|Yj=Y1}B1={Xj|Yj=Y1}. Then the desired quantity will equal

It remains to compute the value of?∑x∈Bi|Xi?x|∑x∈Bi|Xi?x|?for every?ii. The summation involving?yy?can be computed similarly.

What we need to do, restated more simply:

• For integers?x1≤x2≤?≤xnx1≤x2≤?≤xn, compute?si=∑nj=1|xi?xj|si=∑j=1n|xi?xj|?for each?ii.

This can be done in linear time. First, compute?s1s1. Then for all?1≤i<N1≤i<N,?si+1=si+(2i?N)(xi+1?xi).si+1=si+(2i?N)(xi+1?xi).

Overall, the solution runs in?O(NlogN)O(Nlog?N)?time because we first need to sort the?xx-coordinates for each?yy.

 

#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]

以上就是關(guān)于【USACO 2020 February Contest, Silver Problem 2. Triangles】的解答，如需了解學(xué)校/賽事/課程動(dòng)態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

NOAI人工智能奧賽 2026-2027 活動(dòng)章程出爐：新規(guī)則必看！

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動(dòng)：留學(xué)申請(qǐng)的“核武器”來(lái)了！