網(wǎng)址：https://ac.nowcoder.com/acm/contest/4853/B

題目描述

給定平面上n個點(diǎn)的坐標(biāo),并且我們定義兩個點(diǎn)的距離為曼哈頓距離.
曼哈頓距離是指對兩個點(diǎn)(x_1,y_1),(x_2,y_2),他們之間的距離為|x_2 - x_1| + |y_2 - y_1|
.眾所周知三個點(diǎn)可以構(gòu)成一個三角形,那么n個點(diǎn)可以構(gòu)成C(n,3)（組合）個三角形,現(xiàn)在你需要求出所有三角形的周長和 輸出在模998244353意義下的答案.數(shù)據(jù)保證不存在三點(diǎn)共線.

輸入描述:

第一行一個整數(shù)表示n.
接下來n行每行兩個整數(shù)x,y表示一個點(diǎn).

輸出描述:

輸出一個整數(shù)表示周長和.

示例1

輸入
3
0 0
1 0
1 1
輸出
4

備注:

3≤n≤1e3,-1e9≤x,y≤1e9

題解：

這道題的關(guān)鍵在于不存在三點(diǎn)一線，那么對于任意兩個點(diǎn)，都可以與其他n-2個點(diǎn)形成三角形，也就是這兩個點(diǎn)的邊出現(xiàn)在了n-2個三角形中，所以只需要計(jì)算任意兩個邊的距離，并且乘以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天，繼續(xù)加油。