#include <string>
#include <vector>
#include <list>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <sys/time.h>
using namespace std;

#include "MinimumSquare.cpp"

int main(int argc, char **argv)
{
  int i, j;
  int n;
  class MinimumSquare TheClass, *tc;
  long long retval;
  vector <int> x;
  vector <int> y;
  int K;
  istringstream ss;
  string s, line;

  if (argc != 2) { fprintf(stderr, "usage: a.out num (- for stdin -- x on one line, y on the next)\n"); exit(1); }

  if ((string) argv[1] == "-") {
    if (!getline(cin, line)) exit(0);
    ss.clear();
    ss.str(line);
    while (ss >> i) x.push_back(i);
    if (!getline(cin, line)) exit(0);
    ss.clear();
    ss.str(line);
    while (ss >> i) y.push_back(i);
    if (!(cin >> K)) exit(0);
  } else {

    if (atoi(argv[1]) == 0) {
      x.push_back(0);
      x.push_back( 3);
      y.push_back(0);
      y.push_back( 7);
      K = 2;
    }
  
    if (atoi(argv[1]) == 1) {
      x.push_back(-4);
      x.push_back( 3);
      x.push_back( 1);
      y.push_back(3 );
      y.push_back( -1);
      y.push_back( -2);
      K = 2;
    }
  
    if (atoi(argv[1]) == 2) {
      x.push_back(0);
      x.push_back( 0);
      x.push_back( 1);
      x.push_back( 1);
      x.push_back( 2);
      x.push_back( 2);
      y.push_back(0);
      y.push_back( 1);
      y.push_back( 0);
      y.push_back( 1);
      y.push_back( 0);
      y.push_back( 1);
      K = 4;
    }
  
    if (atoi(argv[1]) == 5) {
     x.push_back(15); y.push_back(21);
     x.push_back(9); y.push_back(11);
     x.push_back(15); y.push_back(21);
     x.push_back(11); y.push_back(10);
     x.push_back(10); y.push_back(29);
     x.push_back(16); y.push_back(20);
     x.push_back(11); y.push_back(24);
     x.push_back(2); y.push_back(23);
     x.push_back(11); y.push_back(8);
     x.push_back(26); y.push_back(22);
      K = 4;
    }
  
    if (atoi(argv[1]) == 3) {
      x.push_back(1000000000);
      x.push_back( 1000000000);
      x.push_back( 1000000000);
      x.push_back( -1000000000);
      x.push_back( -1000000000);
      x.push_back( -1000000000);
      y.push_back(1000000000);
      y.push_back( 0);
      y.push_back( -1000000000);
      y.push_back( 1000000000);
      y.push_back( 0);
      y.push_back( -1000000000);
      K = 3;
    }
  
    if (atoi(argv[1]) == 4) {
      x.push_back(-47881);
      x.push_back( 28623);
      x.push_back( 1769);
      x.push_back( -38328);
      x.push_back( -16737);
      x.push_back( 16653);
      x.push_back( -23181);
      x.push_back( 37360);
      x.push_back( 41429);
      x.push_back( 26282);
      x.push_back( 254);
      x.push_back( 728);
      x.push_back( 8299);
      x.push_back( -41080);
      x.push_back( -29498);
      x.push_back( 17488);
      x.push_back( -23937);
      x.push_back( -11);
      x.push_back( 33319);
      x.push_back( 25232);
      y.push_back(-46462);
      y.push_back( 48985);
      y.push_back( -43820);
      y.push_back( -19587);
      y.push_back( -33593);
      y.push_back( -28337);
      y.push_back( 13667);
      y.push_back( -48131);
      y.push_back( -5568);
      y.push_back( -2332);
      y.push_back( -41918);
      y.push_back( -31370);
      y.push_back( -3695);
      y.push_back( 42599);
      y.push_back( -37788);
      y.push_back( -40096);
      y.push_back( 39049);
      y.push_back( 25045);
      y.push_back( -2122);
      y.push_back( 3874);
      K = 8;
    }
  }

  struct timeval t0;
  double t1, t2, total;

   if (atoi(argv[1]) == 6) {
    for (n = 5; n <= 10000; n+= 5) {
      total = 0;
      for (j = 0; j < 5; j++) {
        x.clear();
        y.clear();
        for (i = 0; i < n; i++) { 
          x.push_back(lrand48()%100000000); 
          y.push_back(lrand48()%100000000);
        }
        tc = new MinimumSquare;
        gettimeofday(&t0, NULL);
        t1 = t0.tv_usec;
        t1 /= 1000000.0;
        t1 += t0.tv_sec;
        retval = tc->minArea(x, y, K);
        gettimeofday(&t0, NULL);
        t2 = t0.tv_usec;
        t2 /= 1000000.0;
        t2 += t0.tv_sec;
        total += (t2-t1);
        delete tc;
      }
      printf("%d %.3lf\n", n, total/5.0);
    }
    exit(0);
  }
      

  retval = TheClass.minArea(x, y, K);
  cout << retval << endl;

  exit(0);
}