蓝桥杯2015年第六届真题-广场舞

解题思路: 参考别人的C语言优秀题解了

注意事项:

参考代码:

package dotcpp.数学;
import java.util.Scanner;
public class 广场舞 {
       static int cnt = 0;
       public static void main(String[] args) {
           Scanner in = new Scanner(System.in);
           int n = in.nextInt();
           Point[] points = new Point[n];
           int maxX = 0, minX = 99999999;
           int maxY = 0, minY = 99999999;
           for(int i = 0; i < n; i++) {
               int x = in.nextInt();
               int y = in.nextInt();
               points[i] = new Point(x, y);
               if(points[i].x > maxX) {
                   maxX = points[i].x;
               }
               if(points[i].x < minX) {
                   minX = points[i].x;
               }

               if(points[i].y > maxY) {
                   maxY = points[i].y;
               }
               if(points[i].y < minY) {
                   minY = points[i].y;
               }
           }
           for(int i = minX; i < maxX; i++) {  //x的最小值到最大值
               for(int j = minY; j < maxY; j++) {  //y的最小值到最大值
                   //判读右、下、右下的三个点是否都在范围内
                   if(f(points, i, j) && f(points, i+1, j) && f(points, i, j+1) && f(points, i+1, j+1)) {
                       cnt++;
                   }
               }
           }
           System.out.println(cnt);

       }
       public static boolean f(Point[] points, int x, int y) {
           boolean flag = false;
           /**
            * 由于输入时按顺序的，所以计算还简单了，只需要求出0点-1点、1点-2点、2点-3点、3点-4点、(4点-0点)的斜率即可。
            * 其中4点-0点不好求，这里的做法非常巧妙，首先将j赋为4，先将4点和0点比较，之后 j=i,i++ ,避免了双层嵌套还解决了回环的问题。
            * */
           int j = points.length - 1;
           for(int i = 0; i < points.length; i++) {
               //    两点的y坐标值的最小值                                两点的y坐标值的最大值
               if(y > Math.min(points[i].y, points[j].y) && y <= Math.max(points[i].y, points[j].y)) {
                   //首先确定待判断点，在边界上相邻的两个端点范围内,再运用pnpoly算法来判断
                   //注：pnpoly算法原理：从一个目标点引出一条射线，统计这条射线与对变形的交点个数。
                   // 如果有奇数个交点，则说明目标点在多边形内，若为偶数个交点，则在外。
                   //这题我们的射线是与x轴平行向左
                   double temp = (double) points[i].x + (double)((( y- points[i].y)/ (double)(points[i].y - points[j].y)) * (double)((points[i].x - points[j].x)));//与边界交点
                   if(temp < x)//既然是射线 那位啥改成 > 时结果为6呢？
                       //因为有一个点既是边界点又是砖块的右下点，改成>=就好了
                   {
                       flag = ! flag;
                   }
               }
               j = i;
           }
           return  flag;
       }
   }
class Point {
   int x;
   int y;
   public Point(int x, int y) {
       this.x = x;
       this.y = y;
   }
}