Codeforces Round 500 div2 C.Photo of The Sky - 進捗だめな人のメモ書き

C. Photo of The Sky

問題
n個の星のx,y座標の値が適当に $a_{1},a_{2},...,a_{2n}$ と書かれている。
これらの $a_i$ $(1 \leq i \leq 2n)$ からn個の星の座標 $(x_1,y_1),(x_2,y_2) ,...(x_n,y_n)$ $(x_1 \leq x_2 \leq ...\leq x_n , y_1 \leq y_2 \leq... \leq y_n )$ を作成する。このときn個の星がうつる長方形の考えうる面積 $(x_n-x_1) \times (y_n-y_1)$ の最小値を求めよ。
解法

まず $a_i$ $(1 \leq i \leq 2n)$ を昇順にソートする。
をn個のx座標値の集合とn個のy座標の集合に分割した場合を考えると、に最小値,最大値が入っている場合とに最小値,に最大値が入っている場合が考えられる。そのためそれぞれの場合の面積の最小値を求める必要がある。
- $X$ に最小値 $a_1$ ,最大値 $a_{2_{n}}$ が入っている場合は $i(2 \leq i \leq 2n-1)$ に関して $a_{i+n-1}-a_i$ が最小な $a_i$ が $Y$ の最小値、 $a_{i +n-1}$ が $Y$ の最大値として面積を計算する。
- $X$ に最小値 $a_1$ ,Yに最大値 $a_{2_{n}}$ が入っている場合は, $X$ や $Y$ それぞれの最大値と最小値の差を小さくするために、 $X$ の最大値を $a_n$ , $Y$ の最小値を $a_{n+1}$ として面積を計算する。

ソースコード

#include<iostream>
#include<vector>
#include<stdlib.h>
#include<time.h>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<queue>
#include<map>
#include<iomanip>
using namespace std;

int main(void){
 int x1,x2;
 int y1,y2;
 int a,n;
 long long int ans=9000000000000000000;
 int ok=0;
 long long int sum=0;
 vector<int> A;
 cin>>n;
 for(int i=0; i<2*n; i++){
  cin>>a;
  A.push_back(a);
 }
 sort(A.begin(),A.end());

 x1=A[0];//xに最小値
 x2=A[2*n-1];//xに最大値
 for(int i=1;(i+n-1)<2*n-1; i++){
  y1=A[i]; 
  y2=A[i+n-1]; 
  sum=(long long int)abs(x2-x1)*abs(y1-y2);
  if(sum<ans)ans=sum;
 }

 x1=A[0];//Xに最小値
 y2=A[2*n-1];//Yに最大値

 x2=A[n-1];
 y1=A[n];
 sum=(long long int)abs(x1-x2)*abs(y1-y2);
 if(sum<ans)ans=sum;

 std::cout<<ans<<std::endl;
 return 0;
}

解説