Untitled
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