P6149 [USACO20FEB] Triangles S 总结

P6149 [USACO20FEB] Triangles S 总结

思路历程

这一题还是相当有趣的，首先我们不难发现，题目要求的就是一个两个直角边平行于 \(x\) 和 \(y\) 的直角三角形。

此时我们想到，这个三角形开口的方向可以有四个情况（对应四个象限），所以我们可以排序四次并在这四次排序操作得到这四种情况。

然后我们考虑一个点对应的 \(x\) 轴和 \(y\) 轴上有多个点怎么求面积，我们可以通过推一推式子得到结论：假设 \(x\) 轴上有多个线段 \(x_1, x_2, x_3\) 和 \(y\) 轴上有多段线段 \(y_1, y_2, y_3\)，可以得到这个式子：

\[\sum S = (x_1+2\times x_2+3\times x_3) \times (y_1 + 2\times y_2 + 3\times y_3) \]

所以我们还需要用一个桶来记录出现的点的个数。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long 
#define pii pair <ll, ll>
const ll PI = 1e4+5;
const ll MOD = 1e9+7;void solve () {int n; cin >> n;vector <pii> point(n);for (int i = 0;i < n;i++) {cin >> point[i].first >> point[i].second;point[i].first += PI, point[i].second += PI;}ll ans = 0;auto count = [&]() -> void {vector <ll> x(PI*2+1000, 0), _x(PI*2+1000, 0), y(PI*2+1000, 0), _y(PI*2+1000, 0);vector <ll> lstx(PI*2+1000), lsty(PI*2+1000);for (auto [fir, sec] : point) {x[fir] = (x[fir] + abs(sec-lstx[fir])*_x[fir]) % MOD, _x[fir]++, lstx[fir] = sec;y[sec] = (y[sec] + abs(fir-lsty[sec])*_y[sec]) % MOD, _y[sec]++, lsty[sec] = fir;ans = (ans + x[fir]*y[sec]) % MOD; }};sort(point.begin(), point.end(), [&](pii x, pii y) { return (x.first != y.first ? x.first < y.first : x.second < y.second); });count();sort(point.begin(), point.end(), [&](pii x, pii y) { return (x.first != y.first ? x.first < y.first : x.second > y.second); });count();sort(point.begin(), point.end(), [&](pii x, pii y) { return (x.first != y.first ? x.first > y.first : x.second < y.second); });count();sort(point.begin(), point.end(), [&](pii x, pii y) { return (x.first != y.first ? x.first > y.first : x.second > y.second); });count();cout << ans << "\n";
}int main () {ios::sync_with_stdio(false);cin.tie(nullptr), cout.tie(nullptr);int _ = 1;while (_--) solve();return 0;
}