1039 Pipe

「1039 Pipe」の編集履歴（バックアップ）一覧はこちら

「1039 Pipe」(2006/05/13 (土) 23:44:13) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1039 Pipe
**解答例
 import java.util.*;
 
 public class Main {
     static final double EPS = 1.0E-6;
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             int n = sc.nextInt();
             if(n==0) break;
             
             Point[] ps = new Point[2*n];
             for(int i=0;i<n;i++){
                 double x = sc.nextDouble();
                 double y = sc.nextDouble();
                 ps[2*i] = new Point(x, y);
                 ps[2*i+1] = new Point(x, y-1.0);
             }
             
             double ans = - Double.MAX_VALUE;
             for(int i=0;i<2*n;i++){
                 for(int j=i+1;j<2*n;j++){
                     Point p1 = ps[i];
                     Point p2 = ps[j];
                     if(p1.x==p2.x) continue;
                     
                     double a = (p2.y-p1.y) / (p2.x-p1.x);
                     double b = - a * p1.x + p1.y;
                     
                     double y0 = a * ps[0].x + b;
 
                     // initial point check
                     if(y0>ps[0].y + EPS || ps[1].y-EPS>y0) continue;
                     
                     double impactx = Double.MAX_VALUE;
                     
                     for(int k=1;k<n;k++){
                         double xnow = ps[2*k].x;
                         double ynow = a * xnow + b;
                         double xprev = ps[2*k-2].x;
                         double yprev = a * xprev + b;
                         double ynowsup = ps[2*k].y;
                         double ynowinf = ps[2*k+1].y;
                         double yprevsup = ps[2*k-2].y;
                         double yprevinf = ps[2*k-1].y;
                         if(ynow <= ynowsup + EPS && ynow >= ynowinf - EPS) continue;
                         else if(ynow > ynowsup + EPS){
                             impactx = xprev + (xnow-xprev)*(yprevsup - yprev)/((yprevsup - yprev)+(ynow - ynowsup));
                             break;
                         }
                         else{
                             impactx = xprev + (xnow-xprev)*(yprev - yprevinf)/((yprev - yprevinf)+(ynowinf - ynow));
                             break;
                         }
                     }
                     ans = Math.max(impactx, ans);
                     
                     //System.out.printf("i:%d j:%d min:%f\r\n", i, j, ans);
                 }
             }
             
             if(ans==Double.MAX_VALUE){
                 System.out.println("Through all the pipe.");
             }
             else{
                 System.out.printf("%.2f\r\n", ans);
             }
         }
     }
 }
 
 class Point{
     double x;
     double y;
     public Point(double x, double y) {
         // TODO Auto-generated constructor stub
         this.x = x;
         this.y = y;
     }
 }