Untitled

 avatar
unknown
plain_text
5 months ago
2.6 kB
4
Indexable
import java.util.*;

public class CountPress {

    public static boolean pointInsidePoly(int x, int y, List<int[]> vert) {
        int n = vert.size();
        boolean inside = false;
        for (int i = 0; i < n; i++) {
            int[] v1 = vert.get(i);
            int[] v2 = vert.get((i + 1) % n);
            int x1 = v1[0], y1 = v1[1], x2 = v2[0], y2 = v2[1];
            if ((y1 > y) != (y2 > y) && (x < (x2 - x1) * (y - y1) / (y2 - y1) + x1)) {
                inside = !inside;
            }
        }
        return inside;
    }

    public static int minPress(List<int[]> vert, int brushSize) {
        int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE, minY = Integer.MAX_VALUE, maxY = Integer.MIN_VALUE;
        for (int[] vertex : vert) {
            minX = Math.min(minX, vertex[0]);
            maxX = Math.max(maxX, vertex[0]);
            minY = Math.min(minY, vertex[1]);
            maxY = Math.max(maxY, vertex[1]);
        }

        Set<String> coveredPoints = new HashSet<>();
        int presses = 0;

        for (int x = minX; x <= maxX; x++) {
            for (int y = minY; y <= maxY; y++) {
                if (pointInsidePoly(x, y, vert)) {
                    boolean covered = false;
                    for (int dx = 0; dx < brushSize; dx++) {
                        for (int dy = 0; dy < brushSize; dy++) {
                            if (coveredPoints.contains((x + dx) + "," + (y + dy))) {
                                covered = true;
                                break;
                            }
                        }
                        if (covered) break;
                    }
                    if (!covered) {
                        presses++;
                        for (int dx = 0; dx < brushSize; dx++) {
                            for (int dy = 0; dy < brushSize; dy++) {
                                coveredPoints.add((x + dx) + "," + (y + dy));
                            }
                        }
                    }
                }
            }
        }

        return presses;
    }

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        List<int[]> vert = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int x = scn.nextInt();
            int y = scn.nextInt();
            vert.add(new int[]{x, y});
        }
        int m = scn.nextInt();
        System.out.print(minPress(vert, m));
    }
}
Editor is loading...
Leave a Comment