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 由 温婕莺