2012中南大學校賽F題 - 旋轉卡殼的思維...

​​http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1165​​

       當時做計算機幾何的時候也沒練過旋轉卡殼...對于一類求最小滿足條件的區間問題..這種思維是很重要的...

       就如同本題...實際上就是要使得從a,b,c中取出的數盡量靠近.. 題目所給的a,b,c已經有序...用三個指針x,y,z來記錄目前所在a,b,c的位置..每次在計算完a[x],b[y],c[z]後..将x,y,z都嘗試性的往後移一位..找到min(a[x+1],b[y+1,c[z+1])...并真正移動那一位..直到x=an...b=bn....c=cn....這裡有個比較好的預處理..就是将a[an+1]=oo  b[bn+1]=oo  c[cn+1]=oo 這樣在做指針移動時..就可以不讨論越界問題了...

Program:

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<queue>
#define oo 2000000000
#define ll long long
#define get(a,b,c) (a-b)*(a-b)+(a-c)*(a-c)+(b-c)*(b-c)
using namespace std;
int n[3],x,y,z;
ll s[3][1000005],t,ans,a,b,c;
int main()
{   
       freopen("input.txt","r",stdin);
       freopen("output.txt","w",stdout);
       while (~scanf("%d%d%d",&n[0],&n[1],&n[2]))
       {
              for (y=0;y<3;y++)
              {
                      for (x=1;x<=n[y];x++) scanf("%lld",&s[y][x]);  
                      s[y][x]=oo;
              }
              x=y=z=1;  
              ans=get(s[0][x],s[1][y],s[2][z]);
              while (x<=n[0] && y<=n[1] && z<=n[2])
              { 
                      t=get(s[0][x],s[1][y],s[2][z]);
                      a=s[0][x+1];  b=s[1][y+1];  c=s[2][z+1];
                      if (t<ans) ans=t;
                      if (a<=b && a<=c) x++; else
                      if (b<=a && b<=c) y++; else 
                      z++;
              }
              printf("%lld\n",ans);
       }
       return 0;
}