1408 Fishnet

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

「1408 Fishnet」(2006/04/16 (日) 23:07:11) の最新版変更点

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

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

**1408 Fishnet
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1408
**解答方針
すべての四角形の面積を計算するだけ．工夫があるのは直線の扱い方である．ここでは直線は常に ax + by + c = 0 の形で扱っている．y = ax + b の形で扱うと，y軸平行な直線を特別扱いしなければならないからだ．ax + by + c = 0 の形で扱うと確かに計算が煩雑になるが，基本的な処理をあらかじめて用意しておけば問題ないだろう．

**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         while(true){
             int n = sc.nextInt();
             if(n==0) break;
             double a[] = new double[n+2];
             double b[] = new double[n+2];
             double c[] = new double[n+2];
             double d[] = new double[n+2];
             a[0] = 0.0;
             a[n+1] = 1.0;
             b[0] = 0.0;
             b[n+1] = 1.0;
             c[0] = 0.0;
             c[n+1] = 1.0;
             d[0] = 0.0;
             d[n+1] = 1.0;
             for(int i=1;i<n+1;i++) a[i] = sc.nextDouble();
             for(int i=1;i<n+1;i++) b[i] = sc.nextDouble();
             for(int i=1;i<n+1;i++) c[i] = sc.nextDouble();
             for(int i=1;i<n+1;i++) d[i] = sc.nextDouble();
             Solver sol = new Solver(n,a,b,c,d);
             System.out.printf("%.6f\r\n",sol.solve());
         }
     }
 }
 
 class Solver{
     int n;
     double[] a;
     double[] b;
     double[] c;
     double[] d;
     Solver(int n, double[] a, double[] b, double[] c, double[] d) {
         this.n = n;
         this.a = a;
         this.b = b;
         this.c = c;
         this.d = d;
     }
     public double solve(){
         Line[] ablines = new Line[n+2];
         Line[] cdlines = new Line[n+2];
         for(int i=0;i<n+2;i++){
             ablines[i] = new Line(new Point(a[i],0.0),new Point(b[i],1.0));
             cdlines[i] = new Line(new Point(0.0,c[i]),new Point(1.0,d[i]));
         }
         Point[][] crosspoints = new Point[n+2][n+2];
         for(int i=0;i<n+2;i++){
             for(int j=0;j<n+2;j++){
                 crosspoints[i][j] = ablines[i].crossPoint(cdlines[j]);
             }
         }
         
         double max = Double.MIN_VALUE;
         for(int i=0;i<n+1;i++){
             for(int j=0;j<n+1;j++){
                 Point p1 = crosspoints[i][j];
                 Point p2 = crosspoints[i+1][j];
                 Point p3 = crosspoints[i+1][j+1];
                 Point p4 = crosspoints[i][j+1];
                 double s1 = Point.squareOfTriangle(p1,p2,p3);
                 double s2 = Point.squareOfTriangle(p3,p4,p1);
                 double s = s1+s2;
                 if(s>max) max = s;
             }
         }
         return max;
     }
 }
 
 class Point{
     double x;
     double y;
     Point(double x,double y){
         this.x = x;
         this.y = y;
     }
     public static double squareOfTriangle(Point p1,Point p2,Point p3){
         double x1 = p1.x-p2.x;
         double x2 = p3.x-p2.x;
         double y1 = p1.y-p2.y;
         double y2 = p3.y-p2.y;
         double s = (x1*y2-x2*y1)/2;
         return Math.abs(s);
     }
 }
 
 class Line{
     double a;
     double b;
     double c;
     Line(Point p1,Point p2){
         this.a = p1.y-p2.y;
         this.b = -p1.x+p2.x;
         this.c = p1.x*p2.y-p2.x*p1.y;
     }
     public Point crossPoint(Line l){
         double x = (-l.b*this.c+this.b*l.c)/(this.a*l.b-this.b*l.a);
         double y = (l.a*this.c-this.a*l.c)/(this.a*l.b-this.b*l.a);
         return new Point(x,y);
     }
 }