lib/Documentation/docs-sonyckson/1065.cpp

   1 // ALGORITMO, QUE USA GEMETIA; PARA VER EN UN POLIGONO CONVEXO
   2 //Q PUNTOS ESTAN EN Q TRIANGULO Q CONTENGA PUNTOS ADJACENTES
   3 // FRONTIER, TIMUS :), costo un ojo de la cara! :P :D
   4
   5 #include <algorithm>
   6 #include <cassert>
   7 #include <vector>
   8 #include <set>
   9 #include <string>
  10 #include <fstream>
  11 #include <iostream>
  12 #include <iomanip>
  13 #include <map>
  14 #include <stack>
  15 #include <sstream>
  16 #include <queue>
  17
  18 #include <cmath>
  19 #include <cstdio>
  20 #include <cctype>
  21 #include <cstdlib>
  22 #include <cstring>
  23 #include <cassert>
  24 #define forn(i, n) for(int i=0;i<int(n);i++)
  25 #define foreach(it, c)  for(typeof((c).begin()) it = (c).begin();it!=(c).end();++it)
  26 #define ALL(x)   (x).begin(),(x).end()
  27 #define SORT(x) sort(ALL(x))
  28 using namespace std;
  29 #define VI vector<int>
  30 #define VS vector<string>
  31 #define PB push_back
  32 #define ll long long
  33 int N, M;
  34 int tow[51][2];
  35 int p[1001][2];
  36 double m[1001][2];
  37 bool fijo[51][51][51];
  38 double cruz(int h, int i, int j){
  39         int x1, x2, y1, y2;
  40         x1 = tow[i][0]-p[h][0], x2 = tow[j][0] - p[h][0];
  41         y1 = tow[i][1]-p[h][1], y2 = tow[j][1] - p[h][1];
  42         return fabs((double)x1*y2-x2*y1)/2.0;
  43 }
  44 double cruz2(int h, int i, int j){
  45         int x1, x2, y1, y2;
  46         x1 = tow[i][0]-tow[h][0], x2 = tow[j][0] - tow[h][0];
  47         y1 = tow[i][1]-tow[h][1], y2 = tow[j][1] - tow[h][1];
  48         return fabs((double)x1*y2-x2*y1)/2.0;
  49 }
  50 bool adentro(int pi, int i, int j, int k){
  51         double a1 = cruz(pi,i,j), a2 = cruz(pi,i,k), a3 = cruz(pi,j,k);
  52         if( fabs(a1+a2+a3 - cruz2(i,j,k)) < 1e-7 ) return true;
  53         return false;
  54 }
  55 double cruz3(double x1, double y1, double x2, double y2, double x3, double y3){
  56         double xx1, xx2, yy1, yy2;
  57         xx1 = x2-x1, xx2 = x3-x1;
  58         yy1 = y2-y1, yy2 = y3-y1;
  59         return fabs(xx1*yy2-xx2*yy1);
  60 }
  61 double dist(double x1, double y1, double x2, double y2){
  62         double dx, dy;
  63         dx = x1-x2;
  64         dy = y1-y2;
  65         return sqrt(dx*dx+dy*dy);
  66 }
  67 void f(int ind){
  68         vector<pair<double, int> > vec;
  69         int i ,j ,k;
  70         int ant = (ind+N-1)%N;
  71         for(i=0;i<M;i++){
  72                 double x, y;
  73                 x = (m[i][0]-(double)tow[ind][0]) / dist(tow[ind][0], tow[ind][1], m[i][0], m[i][1]);
  74                 y = (m[i][1]-(double)tow[ind][1]) / dist(tow[ind][0], tow[ind][1], m[i][0], m[i][1]);
  75                 double xa, ya;
  76                 xa = (tow[ant][0]-(double)tow[ind][0]) / (dist(tow[ant][0], tow[ant][1], tow[ind][0], tow[ind][1]));
  77                 ya = (tow[ant][1]-(double)tow[ind][1]) / (dist(tow[ant][0], tow[ant][1], tow[ind][0], tow[ind][1]));
  78                 double d1, d2, d3;
  79                 d1 = dist( xa, ya, x, y);
  80                 d2 = dist(0.0, 0.0, x, y);
  81                 d3 = dist(0.0, 0.0, xa, ya);
  82                 double area = cruz3(x, y, 0.0, 0.0, xa, ya);
  83                 double alt = area / d3;
  84                 double len = sqrt(d2*d2-alt*alt);
  85                 if( d1*d1 + 1e-7 > d2*d2+d3*d3 ){
  86                         vec.PB(make_pair(len+d3, i));
  87                 }else{
  88                         vec.PB(make_pair(d3-len, i));
  89                 }
  90         }
  91         sort(vec.begin(), vec.end());
  92         reverse(vec.begin(), vec.end());
  93         int v = 0;
  94         int tri = (ind+1)%N;
  95         while(v != M && tri != ant){
  96                 int w = vec[v].second;
  97                 int aux  = (tri+1)%N;
  98                 if( adentro(w, ind, tri, aux) ){
  99                         fijo[ind][tri][aux] = fijo[ind][aux][tri] = true;
 100                         fijo[tri][ind][aux] = fijo[tri][aux][ind] = true;
 101                         fijo[aux][ind][tri] = fijo[aux][tri][ind] = true;
 102                         if( aux != ant && adentro(w, ind, aux, (aux+1)%N) ) tri = aux;
 103                         else v++;
 104                 }else tri = aux;
 105         }
 106 }
 107 bool visited[51][51][51];
 108 double b[51][51][51];
 109 double back(int last, int tamos, int vamos){
 110         if( tamos == vamos ) return dist(tow[last][0], tow[last][1], tow[tamos][0], tow[tamos][1]);
 111         if( visited[last][tamos][vamos] ) return b[last][tamos][vamos];
 112         visited[last][tamos][vamos] = true;
 113         double & res = b[last][tamos][vamos];
 114         res = back(tamos, (tamos+1)%N, vamos) + dist(tow[last][0], tow[last][1], tow[tamos][0], tow[tamos][1]);
 115         if(!fijo[last][tamos][(tamos+1)%N]){
 116                 res = min( res, back(last, (tamos+1)%N, vamos));
 117         }
 118         return res;
 119 }
 120 int main(){
 121         int i,j ,k;
 122         scanf("%i %i", &N, &M);
 123         for(i=0;i<N;i++)scanf("%i %i",&tow[i][0], &tow[i][1]);
 124         for(i=0;i<M;i++)scanf("%i %i",&p[i][0], &p[i][1]);
 125         memset(fijo, false, sizeof(fijo));
 126         for(i=0;i<M;i++) for(j=0;j<2;j++) m[i][j] = (double) p[i][j];
 127         for(i=0;i<N;i++) f( i );
 128         double res = 1000000000000.0;
 129         memset(visited, false, sizeof(visited));
 130         for(i=0;i<N;i++)for(j=i+1;j<N;j++)for(k=j+1;k<N;k++){
 131                 if( cruz3(tow[i][0], tow[i][1], tow[j][0], tow[j][1], tow[k][0], tow[k][1])/ 2.0 < 1e-7 ) continue;
 132                 double aux = back(i, (i+1)%N, j) + back(j, (j+1)%N, k) + back(k, (k+1)%N, i);
 133                 res = min( res, aux );
 134         }
 135         if( res > 10000000000.0 ) while(1);
 136         printf("%.2lf\n", res);
 137         return 0;
 138 }