Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Rectangle {
- int x1
- int y1
- int x2
- int y2
- Rectangle(int x1, int y1, int x2, int y2) {
- this.x1 = x1
- this.y1 = y1
- this.x2 = x2
- this.y2 = y2
- }
- int width() {
- return x2 - x1
- }
- int height() {
- return y2 - y1
- }
- int area() {
- return width() * height()
- }
- @Override
- String toString() {
- return "Rect($x1; $y1; $x2; $y2)".toString()
- }
- }
- class Dot {
- int x
- int y
- Dot(int x, int y) {
- this.x = x
- this.y = y
- }
- @Override
- String toString() {
- return "Dot($x; $y)".toString()
- }
- }
- class Pair<T> {
- T first
- T second
- private Pair(T first, T second) {
- this.first = first
- this.second = second
- }
- static final <T> Pair<T> of(T first, T second) {
- return new Pair<>(first, second)
- }
- @Override
- String toString() {
- return "Pair[$first, $second]".toString()
- }
- }
- List<List<Rectangle>> split(Rectangle rectangle, Integer area) {
- if (area == rectangle.area()) {
- return [[rectangle]]
- }
- if (rectangle.area() % area != 0) {
- return []
- }
- List<List<Rectangle>> result = []
- for (Pair<Rectangle> pair : splitter(rectangle, area)) {
- def first = split(pair.first, area)
- def second = split(pair.second, area)
- for (List<Rectangle> firstsList : first) {
- for (List<Rectangle> secondsList : second) {
- if (firstsList && secondsList) {
- result.add(firstsList + secondsList)
- }
- }
- }
- }
- return result
- }
- List<Pair<Rectangle>> splitter(Rectangle r, Integer area) {
- def result = new ArrayList<Pair<Rectangle>>()
- if (area % r.width() == 0 || r.width() % area == 0) {
- Integer mult = (int) (area / r.width()) ?: 1
- for (int cur = mult + r.y1; cur < r.y2; cur += mult) {
- result << Pair.of(new Rectangle(r.x1, r.y1, r.x2, cur), new Rectangle(r.x1, cur, r.x2, r.y2))
- }
- }
- if (area % r.height() == 0 || r.height() % area == 0) {
- Integer mult = (int) (area / r.height()) ?: 1
- for (int cur = mult + r.x1; cur < r.x2; cur += mult) {
- result << Pair.of(new Rectangle(r.x1, r.y1, cur, r.y2), new Rectangle(cur, r.y1, r.x2, r.y2))
- }
- }
- return result.unique()
- }
- def solve(Rectangle base, List<Dot> dots) {
- if (base.area() % dots.size() != 0) {
- println('No solution')
- return
- }
- int targetArea = (int) (base.area() / dots.size())
- def possibleSolutions = split(base, targetArea)
- def solution = possibleSolutions.find { List<Rectangle> solution ->
- def bad = solution.find { Rectangle rect ->
- dots.findAll { Dot dot ->
- dot.x >= rect.x1 && dot.x < rect.x2 && dot.y >= rect.y1 && dot.y < rect.y2
- }.size() != 1
- }
- return !bad
- }
- if (!solution) {
- println('No solution')
- return
- }
- println solution
- }
- def rect = new Rectangle(0, 0, 6, 8)
- def dots = [new Dot(0, 5), new Dot(3, 4), new Dot(5, 7), new Dot(0, 0)]
- solve(rect, dots)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement