牛客练习赛60——B三角形周长和

网址：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;
} 

打卡第16天，继续加油。