网址:https://ac.nowcoder.com/acm/contest/4743/B

题目描述

在牛国有n个小镇编号{1,2,3...n-1,n}1,2,3...n−1,n。用二维平面来表示每个小镇的位置,第i个
小镇的位置为(x_i,y_i)牛能做为牛国的国王,决定给小镇之间建设一些道路,以便于任意小镇
之间都能相互到达,在第i个小镇和第j个小镇之间建设一条道路的花费是|x_i * x_i * y_i-x_j * x_j * y_j+y_i * y_i * (y_i-2*x_i)-y_j * (y_j-2 * x_j)|,但是牛能小气的很,他想最小化建设的费用。

输入描述:

第一行输入一个整数n
接下来n行每行两个整数(x_i,y_i)表示第i个小镇的坐标。

输出描述:

输出一个整数表示最小的花费。

示例

输入
3
1 4
2 8
3 6
输出
252

备注:

1<=n,x,y<=1e5

题解

这道题比赛时怎么也没有做对,还是赛后看了题解才会的

AC代码

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int n;
long long int x,y;
long long int v[100005];
cin>>n;
for(int i=1;i<=n;i++){
    cin>>x>>y;
    v[i]=x*x*y+y*y*y-2*y*y*x;
}
sort(v+1,v+1+n);
cout<<v[n]-v[1]<<endl;
/*相当于
long long int sum=0;
for(int i=1;i<n;i++){
    sum+=(v[i+1]-v[i]);
} */
return 0;

}

注:

这道题自己多看看,警醒警醒自己,当时为什么没有做出来

打卡第二天,希望自己可以一直坚持下去