第七届蓝桥杯Java/A组第五题

题目：

广场舞

LQ市的市民广场是一个多边形，广场上铺满了大理石的地板砖。

地板砖铺得方方正正，就像坐标轴纸一样。
以某四块砖相接的点为原点，地板砖的两条边为两个正方向，一块砖的边长为横纵坐标的单位长度，则所有横纵坐标都为整数的点都是四块砖的交点（如果在广场内）。

广场的砖单调无趣，却给跳广场舞的市民们提供了绝佳的参照物。每天傍晚，都会有大批市民前来跳舞。
舞者每次都会选一块完整的砖来跳舞，两个人不会选择同一块砖，如果一块砖在广场边上导致缺角或者边不完整，则没人会选这块砖。
（广场形状的例子参考【图1.png】）

现在，告诉你广场的形状，请帮LQ市的市长计算一下，同一时刻最多有多少市民可以在广场跳舞。

【输入格式】
输入的第一行包含一个整数n，表示广场是n边形的（因此有n个顶点）。
接下来n行，每行两个整数，依次表示n边形每个顶点的坐标（也就是说广场边缘拐弯的地方都在砖的顶角上。数据保证广场是一个简单多边形。

【输出格式】
输出一个整数，表示最多有多少市民可以在广场跳舞。

【样例输入】
5
3 3
6 4
4 1
1 -1
0 4

【样例输出】
7

【样例说明】
广场如图1.png所示，一共有7块完整的地板砖，因此最多能有7位市民一起跳舞。

【数据规模与约定】
对于30%的数据，n不超过100，横纵坐标的绝对值均不超过100。
对于50%的数据，n不超过1000，横纵坐标的绝对值均不超过1000。
对于100%的数据，n不超过1000，横纵坐标的绝对值均不超过100000000（一亿）。


资源约定：
峰值内存消耗 < 256M
CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。

第七届蓝桥杯Java/A组第五题

思路：

1.找到图形整体所在的X区间

2.将图像的顶点存在一个set集合中，由于不懂如何在set中存二元坐标，所以定义了内部类point 含有两个属性x,y 。

3. 由顶点坐标依次遍历每一条边，找到每一条线段，在X区间的每一个x值对应的y值，并将其存在map 中

4. 然后通过y值上下的减法，得到每个x值有效的坐标点的数量

5.通过坐标点的数量求小矩形的面积：两个相邻的x值组成的坐标块数量= min(两个有效坐标的的数量）-1；

6.加和得出result

代码如下：

package come_on;

import java.util.*;

public class Fifth {
    static int x_start;
    static int x_end;
    static class point{
        float x;
        float y;
        public point(float x, float y){
            this.x=x;
            this.y=y;
        }
    }

    public static void main(String args[]){
        ArrayList<point> list = new ArrayList<>();

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();
       for(int i=0;i<n;i++){
           point points = new point(scanner.nextInt(),scanner.nextInt());
           scanner.nextLine();
           list.add(points);
       }
        Set<point> set = new HashSet<>();
        x_start = (int)list.get(0).x;
        x_end= (int)list.get(0).x;
        for(int i=0;i<5;i++){
           float x1 = list.get(i).x;
           float y1 = list.get(i).y;
           float x2,y2;

           if(x_start>=(int)x1) x_start= (int)x1;
           if(x_end<=(int)x1) x_end= (int)x1;
           if(i!=list.size()-1){
                x2 = list.get(i+1).x;
                y2 = list.get(i+1).y;
           }
           else {
                x2 = list.get(0).x;
                y2 = list.get(0).y;
           }
           for(float x0=Math.min(x1,x2);x0<Math.max(x1,x2);x0++){
               float y0 =(y1-y2)/(x1-x2)*(x0-x1)+y1;
               point point_x = new point(x0,y0);
               set.add(point_x);
               }
        }

        Map<Integer,Integer> map = new TreeMap<>();
        map.put(x_start,0);
        map.put(x_end,0);

       for(point p:set){
           float x0 = p.x;
           float y0 =p.y;
           for(point p0:set){
               float x00 =p0.x;
               float y00 =p0.y;
               if(x00==x0&&y0>y00){
                   map.put((int)x0,(int)((int)y0-y00)+1);
               }
           }
       }
       int result =0;
       for(int i =x_start;i<x_end-1;i++){
           if(map.get(i)!=null&&map.get(i+1)!=null){
               int q = Math.min(map.get(i),map.get(i+1))-1;
               if(q>=0) result+=q;
           }
       }
       System.out.println(result);
    }
}

这道题没有查看答案，做了大概有四个小时，感觉自己的不足还很多，继续加油。

同样还有个问题没有搞懂（百度也没有查到），希望大神指点一二：

set集合用迭代器输出自定义对象point的时候，打印出来的是地址，但是用for循环输出的时候就没有这个问题，不知道是为什么。

以及还有什么更好的想法或者思路欢迎交流讨论。

第七届蓝桥杯Java/A组 第五题

相关推荐

第七届蓝桥杯Java/A组第五题