Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.Comparator;
- import java.util.HashMap;
- import java.util.LinkedHashMap;
- import java.util.Map;
- import java.util.Map.Entry;
- import java.util.Scanner;
- public class Bilsem5 {
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- int koordinatSayisi = Integer.parseInt(in.nextLine());
- LinkedHashMap<Integer, Integer> koordinatListesi = new LinkedHashMap<>();
- int maxX = 0;
- int maxY = 0;
- for (int i = 0; i < koordinatSayisi; i ++) {
- ArrayList<String> raf = getListFromStrSeperatedBy(in.nextLine(), " ", true);
- koordinatListesi.put(Integer.parseInt(raf.get(0)), Integer.parseInt(raf.get(1)));
- if (Integer.parseInt(raf.get(0)) > maxX) {
- maxX = Integer.parseInt(raf.get(0));
- }
- if (Integer.parseInt(raf.get(1)) > maxY) {
- maxY = Integer.parseInt(raf.get(1));
- }
- }
- in.close();
- int[][] koordinatlar = new int[maxX + 1][maxY + 1];
- boolean first = true;
- for (Entry<Integer, Integer> entry: koordinatListesi.entrySet()) {
- if (first) {
- koordinatlar[entry.getKey()][entry.getValue()] = 3;
- } else {
- koordinatlar[entry.getKey()][entry.getValue()] = 1;
- }
- }
- CoordinateList list = new CoordinateList();
- for (Entry<Integer, Integer> entry: koordinatListesi.entrySet()) {
- double distanceFromOrigin = Math.sqrt((double) Math.pow(entry.getValue(), 2.0) + (double)Math.pow(entry.getKey(), 2.0));
- list.addCoordinate(new Coordinate(entry.getKey(), entry.getValue(), distanceFromOrigin));
- }
- list.sortList();
- koordinatListesi = new LinkedHashMap<>();
- for (int i = 0; i < list.getSize(); i++) {
- koordinatListesi.put(list.getCoordinate(i).getX(), list.getCoordinate(i).getY());
- }
- int toplamAlan = 0;
- while (!checkIfDone(koordinatlar)) {
- for (Entry<Integer, Integer> entry: koordinatListesi.entrySet()) {
- list = new CoordinateList();
- for (Entry<Integer, Integer> entry2: koordinatListesi.entrySet()) {
- if (entry.equals(entry2)) {
- continue;
- }
- double alan = (double) Math.abs(entry2.getValue() - entry.getValue()) * (double) Math.abs(entry2.getKey() - entry.getKey());
- list.addCoordinate(new Coordinate(entry2.getKey(), entry2.getValue(), alan));
- }
- list.sortList();
- for (int i = 0; i < list.getSize(); i++) {
- boolean cakisma = false;
- Coordinate end = list.getCoordinate(i);
- int startX = entry.getKey();
- int startY = entry.getValue();
- int endX = end.getX();
- int endY = end.getY();
- if (endX < startX) {
- int temp = endX;
- startX = endX;
- endX = temp;
- }
- if (endY < startY) {
- int temp = endY;
- startY = endY;
- endY = temp;
- }
- if (koordinatlar[entry.getKey()][entry.getValue()] == 2 && koordinatlar[end.getX()][end.getY()] == 2
- || koordinatlar[entry.getKey()][entry.getValue()] == 3 && koordinatlar[end.getX()][end.getY()] == 2
- || koordinatlar[entry.getKey()][entry.getValue()] == 2 && koordinatlar[end.getX()][end.getY()] == 3
- || koordinatlar[entry.getKey()][entry.getValue()] == 3 && koordinatlar[end.getX()][end.getY()] == 3) {
- continue;
- }
- for (int a = startX + 1; a < endX; a++) {
- for (int b = startY + 1; b < endY; b++) {
- if (koordinatListesi.containsKey(a) && koordinatListesi.get(a).equals(b)) {
- cakisma = true;
- break;
- }
- }
- if (cakisma) {
- break;
- }
- }
- if (!cakisma) {
- System.out.println("(" + entry.getKey() + ", " + entry.getValue() + ") Eslesme (" + end.getX() + ", " + end.getY() + "): " + list.getCoordinate(i).getArea());
- toplamAlan += list.getCoordinate(i).getArea();
- if (koordinatlar[entry.getKey()][entry.getValue()] == 3 || koordinatlar[end.getX()][end.getY()] == 3) {
- koordinatlar[entry.getKey()][entry.getValue()] = 3;
- koordinatlar[end.getX()][end.getY()] = 3;
- }
- koordinatlar[entry.getKey()][entry.getValue()] = 2;
- koordinatlar[end.getX()][end.getY()] = 2;
- break;
- }
- }
- }
- }
- HashMap<Integer, Integer> unfinished;
- while ((unfinished = checkIfConnected(koordinatlar)) != null) {
- }
- System.out.println(toplamAlan);
- }
- public static boolean checkIfDone(int[][] koordinatlar) {
- boolean done = true;
- for (int i = 0; i < koordinatlar.length; i++) {
- for (int j = 0; j < koordinatlar[i].length; j++) {
- if (koordinatlar[i][j] == 1) {
- done = false;
- break;
- }
- }
- if (!done) {
- break;
- }
- }
- return done;
- }
- public static HashMap<Integer, Integer> checkIfConnected(int[][] koordinatlar) {
- boolean done = true;
- HashMap<Integer, Integer> list = new HashMap<Integer, Integer>();
- for (int i = 0; i < koordinatlar.length; i++) {
- for (int j = 0; j < koordinatlar[i].length; j++) {
- if (koordinatlar[i][j] == 2) {
- done = false;
- list.put(i, j);
- }
- }
- }
- if (done) {
- return null;
- }
- return list;
- }
- public static ArrayList<String> getListFromStrSeperatedBy(String str, String seperate, boolean trimResult) {
- ArrayList<String> list = new ArrayList<>();
- while (str.length() > 0) {
- if (str.contains(seperate)) {
- if (trimResult) {
- list.add(str.substring(0, str.indexOf(seperate)).trim());
- } else {
- list.add(str.substring(0, str.indexOf(seperate)));
- }
- str = str.substring(str.indexOf(seperate) + seperate.length());
- while (str.indexOf(seperate) == 0) {
- str = str.substring(str.indexOf(seperate) + seperate.length());
- }
- } else {
- if (trimResult) {
- list.add(str.trim());
- }
- str = "";
- }
- }
- return list;
- }
- public static class Coordinate{
- int x;
- int y;
- double area;
- public Coordinate(int x, int y, double area) {
- this.x = x;
- this.y = y;
- this.area = area;
- }
- public int getX() {
- return x;
- }
- public int getY() {
- return y;
- }
- public double getArea() {
- return area;
- }
- }
- public static class CoordinateList{
- ArrayList<Coordinate> coordinates;
- public CoordinateList() {
- coordinates = new ArrayList<>();
- }
- public void addCoordinate(Coordinate co) {
- coordinates.add(co);
- }
- public Coordinate getCoordinate(int index) {
- return coordinates.get(index);
- }
- public int getSize() {
- return coordinates.size();
- }
- public void sortList() {
- Collections.sort(coordinates, new Comparator<Coordinate>() {
- public int compare(Coordinate c1, Coordinate c2) {
- if (c1.getArea() == c2.getArea()) {
- return 0;
- } else if (c1.getArea() > c2.getArea()) {
- return 1;
- } else {
- return -1;
- }
- }
- });
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement