网址: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;
}
注:
这道题自己多看看,警醒警醒自己,当时为什么没有做出来