网址:https://ac.nowcoder.com/acm/contest/4853/B
题目描述
给定平面上n个点的坐标,并且我们定义两个点的距离为曼哈顿距离.
曼哈顿距离是指对两个点(x_1,y_1),(x_2,y_2),他们之间的距离为|x_2 - x_1| + |y_2 - y_1|
.众所周知三个点可以构成一个三角形,那么n个点可以构成C(n,3)(组合)个三角形,现在你需要求出所有三角形的周长和 输出在模998244353意义下的答案.数据保证不存在三点共线.
输入描述:
第一行一个整数表示n.
接下来n行每行两个整数x,y表示一个点.
输出描述:
输出一个整数表示周长和.
示例1
输入
3
0 0
1 0
1 1
输出
4
备注:
3≤n≤1e3,-1e9≤x,y≤1e9
题解:
这道题的关键在于不存在三点一线,那么对于任意两个点,都可以与其他n-2个点形成三角形,也就是这两个点的边出现在了n-2个三角形中,所以只需要计算任意两个边的距离,并且乘以n-2再取余就是最后的答案。
AC代码
#include<iostream> #include<cmath> using namespace std; #define ll long long int ll sum=0; const ll maxn=998244353; int main(){ ll n,a[1000][2]; cin>>n; for(int i=0;i<n;i++) cin>>a[i][0]>>a[i][1]; for(int i=0;i<n;i++){ for(int j=i+1;j<n;j++){ sum=sum+(abs(a[i][0]-a[j][0])+abs(a[i][1]-a[j][1]))*(n-2); sum%=maxn; } } cout<<sum<<endl; return 0; }