http://livearchive.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=3139

Posted by btc on March Tue 27th 7:18 PM - Never Expires| View : 80
Syntax: CPP
1555 characters | 63 lines | 1.52 KB
DOWNLOAD | RAW | EMBED | CREATE NEW VERSION OF THIS PASTE | REPORT ABUSE | x
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <vector>
  5. #include <utility>
  6. #include <algorithm>
  7.  
  8. #define inf (1 << 30)
  9.  
  10. using namespace std;
  11.  
  12. int main(){
  13.         //freopen("a.in", "r", stdin);
  14.         int n, noCase = 1;
  15.         while(scanf("%d", &n) && n != 0){
  16.                 vector < pair < int, int> > P(n);
  17.                 for(int i=0; i<n; i++)
  18.                         scanf("%d%d", &P[i].first, &P[i].second);
  19.                
  20.                 double D, Dmin = inf, Dmax = 0;
  21.                 for(int i=0; i<n; i++){
  22.                         for(int j=i+1; j<n; j++){
  23.                                 //crear recta
  24.                                 int x1 = P[i].first, y1 = P[i].second, x2 = P[j].first, y2 = P[j].second;
  25.                                 int tipoRecta = 0;
  26.                                 double m = 0, b;
  27.                                 if(x1 == x2){
  28.                                         tipoRecta = 1;
  29.                                         b = x1;
  30.                                 }else if(y1 == y2){
  31.                                         tipoRecta = 2;
  32.                                         b = y1;
  33.                                 }else{
  34.                                         tipoRecta = 3;
  35.                                         m = (y1-y2) * 1.0 / (x1-x2);
  36.                                         b = y1 - m * x1;
  37.                                 }
  38.                                 //ver que todos los puntos esten debajo o encima de la recta
  39.                                 int up = 0, zeros = 0;       
  40.                                 //calcular maxima distancia
  41.                                 D = 0;
  42.                                 for(int k=0; k<n; ++k){
  43.                                         if(k == i || k == j) continue;
  44.                                         if(tipoRecta == 1){
  45.                                                 Dmax = P[k].first - x1;
  46.                                         }else if(tipoRecta == 2){
  47.                                                 Dmax = P[k].second - y1;
  48.                                         }else Dmax = (m * P[k].first - P[k].second + b) / sqrt(m*m + 1);
  49.                                         if(abs(Dmax) <= 1E-8) zeros ++;
  50.                                         else up += (Dmax > 0);
  51.                                         //distancia punto en Dmax
  52.                                         D = max(D, abs(Dmax));
  53.                                 }
  54.                                
  55.                                 if(up == n - 2 - zeros || up == 0)      Dmin = min(Dmin, D);
  56.                         }
  57.                 }
  58.                 Dmin *= 100;
  59.                 Dmin = ceil(Dmin);
  60.                 printf("Case %d: %.2lf\n", noCase++, Dmin/100);
  61.         }
  62.         return 0;
  63. }