題目傳送

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K 64bit IO Format:%lld

題目描述

輸入描述:
輸入描述

第一行一個整數表示n. 接下來n行每行兩個整數x,y表示一個點.

輸出描述:

輸出一個整數表示周長和.

示例1
輸入

3 0 0 1 0 1 1

輸出

4

備注:

3≤n≤1e3
?1e9≤x,y≤1e9
題解：
又到了找規律的時間：
n個點構成C³n個三角形，注意由沒有三點共線，說明任意三個點都可以構成三角形
比如有n個點，現將每兩點之間的馬哈頓距離算出來，并求出總值sum。
然后構建三角形，選取兩個點A和B，那第三個點就可以從剩下（n-2）個點里找，也就是有（n-2）個選擇 ，那A與B之間的這個邊就被用了（n-2）次，然后另外兩個點，再這樣操作。你會發現每個邊都被用了（n-2）次
所以最后結果就是sum*（n-2）

千萬不要忘了 mod
代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const int mod=998244353; ll a[1004]; ll b[1004]; ll w(ll x1,ll y1,ll x2,ll y2) {return abs(x2-x1)+abs(y2-y1); } int main() {int n;ll sum=0;cin>>n;for(int i=1;i<=n;i++){cin>>a[i]>>b[i];}for(int i=1;i<=n;i++){for(int j=i+1;j<=n;j++){sum=(sum+w(a[i],b[i],a[j],b[j]))%mod;}}cout<<sum*(n-2)%mod;return 0; }

總結

以上是生活随笔為你收集整理的三角形周长和【牛客网】牛客网练习赛60的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。