CodeForces 800B Volatile Kite(点与直线的距离)(Java 实现)

如果想要一个凸多边形不退化为凹多边形，那么任意的相邻的三个点必然最多形成一条直线。因此我们可以求出点i-1和i+1的直线向量，再求点i到这条直线的距离，答案必然是取其中最小的一个值

import java.io.*;

import java.util.*;

public class Main {

	static class Point {

		double x,y;

	    Point(double xx,double yy)  {

	        x=xx;

	        y=yy;

	    }

	    Point(){

	    	x=0;

	    	y=0;

	    }

	    Point subtract(final Point b)

	    {

	        return new Point(x-b.x,y-b.y);

	    }

	    Point add(final Point b)

	    {

	        return new Point(x+b.x,y+b.y);

	    }

	    double multiply(final Point b)

	    {

	        return x*b.y-b.x*y;

	    }

	    double dis(final Point b)

	    {

	        return Math.sqrt((x-b.x)*(x-b.x)+(y-b.y)*(y-b.y));

	    }

	}

	static final int N = 10005;

    static final int inf= 0x3f3f3f3f;

    static Point a[]=new Point[N];

	public static void main(String[] args) throws IOException {

		Scanner cin = new Scanner(new InputStreamReader(System.in));

		while(cin.hasNext()){

			int n=cin.nextInt();

			for(int i=0;i<n;i++){

				if(a[i]==null) a[i]=new Point();

				a[i].x=cin.nextDouble();

				a[i].y=cin.nextDouble();

			}

			for(int i=n;i<2*n;i++){

				a[i]=a[i-n];

			}

			double ans=Double.MAX_VALUE;

		    for(int i=0; i<n; i++)

		    {

		        double tmp=a[i+2].subtract(a[i]).multiply(a[i+1].subtract(a[i]))/2;

		        if(a[i].dis(a[i+2])==0) continue;

		        ans=Math.min(ans,tmp/a[i].dis(a[i+2]));

		    }

		    System.out.printf("%.7f\n",ans);

		}

		cin.close();

	}

}

巴特西

CodeForces 800B Volatile Kite(点与直线的距离)(Java 实现)

CodeForces 800B Volatile Kite(点与直线的距离)(Java 实现)

最新文章

热门文章