題目鏈接：點擊查看

題目大意：給出四個點，問最少移動多少步，可以使得四個點圍成的矩形是正方形（這里的正方形允許退化成點）

題目分析：比賽時寫了個三分，然鵝又雙叒叕不知道哪里寫崩了，還是太鶸了呀

首先對于四個點全排列，枚舉每個點分別屬于正方形的哪個位置，方便起見我設：p[ 0 ] 是左上角，p[ 1 ] 是右上角，p[ 2 ] 是左下角，p[ 3 ] 是右下角

不難看出 x 坐標與 y 坐標是相互獨立的，所以這里只討論如何求解最優的 x，關于 y 的話類比過去就好了

對于最終的正方形來說，p[ 0 ] 和 p[ 2 ] 的 x 坐標最終一定是相等的，同理 p[ 1 ] 和 p[ 3 ] 的 x 坐標也一定是相等的，我們將最終相等的兩個 x 坐標分別記為 x1 和 x2

所以具象化一下最終的距離公式為：

不難看出，如果滿足?時，p[ 0 ] 和 p[ 2 ] 的貢獻最小，為?，對于 x2 同理

所以正方形上下兩條平行于 x 軸的邊的長度為?，其取值范圍根據 x1 和 x2 的定義域也不難推出

同理求出?，注意，這兩個絕對值對應的分別是正方形邊長的取值范圍，然后分兩種情況討論一下：

如果和存在交集的話，那么一定存在著一種取值作為正方形的邊長，使得答案為

如果和不存在交集的話，那么需要使或中的一個不在“貢獻最小”的范圍內，針對于 x 討論一下，如果離開這個最優范圍 1 個單位，會對答案多貢獻 2 個單位（因為每條邊需要有兩個點與其對齊）

剩下的封裝一下函數然后按照順序實現下來就好了

代碼：

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=1e6+100;struct Node {LL x,y;void input(){scanf("%lld%lld",&x,&y);} }p[4];int id[4];pair<LL,LL>get_seg(LL a,LL b) {return make_pair(min(a,b),max(a,b)); }pair<LL,LL>get_interval(pair<LL,LL>a,pair<LL,LL>b) {return make_pair(max({0LL,a.first-b.second,b.first-a.second}),max({0LL,b.second-a.first,a.second-b.first})); }LL get_len(pair<LL,LL>a) {return a.second-a.first; }int main() { #ifndef ONLINE_JUDGE // freopen("data.ans.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){for(int i=0;i<4;i++){p[i].input();id[i]=i;} // 01 // 23LL ans=inf;do{LL cur=0;auto x1=get_seg(p[id[0]].x,p[id[2]].x);auto x2=get_seg(p[id[1]].x,p[id[3]].x);auto Seg_x=get_interval(x1,x2);cur+=get_len(x1)+get_len(x2);auto y1=get_seg(p[id[0]].y,p[id[1]].y);auto y2=get_seg(p[id[2]].y,p[id[3]].y);auto Seg_y=get_interval(y1,y2);cur+=get_len(y1)+get_len(y2);LL delta=max(max(Seg_x.first,Seg_y.first)-min(Seg_x.second,Seg_y.second),0LL);cur+=2*delta;ans=min(ans,cur);}while(next_permutation(id,id+4));printf("%lld\n",ans);}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1455E Four Points(数学+几何)的全部內容，希望文章能夠幫你解決所遇到的問題。

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