璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


icpc:problems:usaco20feb_triangles_s
problems
名称Triangles S
题目编号USACO20FEB_S2
题目链接luogu.com.cn/…
来源USACO
算法分类数学
难易程度容易

Triangles S

想法

思考如何计算对于点$ (x,y) $为直角点的直角三角形,先考虑左下角:在直角坐标系中同行的点与同列的点,观察左边的距离与下方的距离。可以计算出总的公式为:$ ( 4 * x_4 + 3 * x_3 + 2 * x_2 + 1 * x_1 ) * ( 4 * y_4 + 3 * y_3 + 2 * y_2 + 1 * y_1 ) $。故排两次序,每次排序后统计两项。

代码实现

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
 
const int N = 1e5+10;
const int mod = 1e9 + 7;
struct node{
	int x, y;
	long long int sumx, sumy;
};
node line[N];
int n;
long long int ans;
 
bool cmp1(node a, node b) {
	return a.x < b.x || (a.x == b.x && a.y < b.y);
}
 
bool cmp2(node a, node b) {
	return a.y < b.y || (a.y == b.y && a.x < b.x);
}
 
void turn() {
	for (int i = 1; i <= n; ++i) {
		int tempx = line[i].x, tempy = line[i].y;
		line[i].x = tempy; line[i].y = - tempx;
		line[i].sumx = 0; line[i].sumy = 0;
	}
	return ;
}
 
void sum() {
	sort(line + 1, line + 1 + n, cmp1);
	int cnt = 0;
	for (int i = 2; i <= n; ++i) {
		if(line[i].x == line[i-1].x) {
			cnt ++;
			line[i].sumx = (line[i-1].sumx + cnt * (line[i].y - line[i-1].y) % mod) % mod;
		}
		else
			cnt = 0;
	}
	sort(line + 1, line + 1 + n, cmp2);
	cnt = 0;
	for (int i = 2; i <= n; ++i) {
		if(line[i].y == line[i-1].y) {
			cnt ++;
			line[i].sumy = (line[i-1].sumy + cnt * (line[i].x - line[i-1].x) % mod ) % mod;
		}
		else
			cnt = 0;
	}
	for (int i = 1; i <= n; ++i) {
		ans = (ans + line[i].sumx * line[i].sumy % mod) % mod;
	}
	return ;
}
 
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) {
		scanf("%d %d", &line[i].x, &line[i].y);
	}
	sum();
	turn();
	sum();
	turn();
	sum();
	turn();
	sum();
 
	printf("%lld", ans);
	return 0;
}
/app/www/public/data/pages/icpc/problems/usaco20feb_triangles_s.txt · 最后更改: 2023/06/09 15:22 由 温婕莺