Advertisement
Guest User

Untitled

a guest
Feb 18th, 2015
232
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.66 KB | None | 0 0
  1. import java.util.ArrayList;
  2. import java.util.Collections;
  3. import java.util.Comparator;
  4. import java.util.HashMap;
  5. import java.util.LinkedHashMap;
  6. import java.util.Map;
  7. import java.util.Map.Entry;
  8. import java.util.Scanner;
  9.  
  10. public class Bilsem5 {
  11.  
  12. public static void main(String[] args) {
  13. Scanner in = new Scanner(System.in);
  14. int koordinatSayisi = Integer.parseInt(in.nextLine());
  15. LinkedHashMap<Integer, Integer> koordinatListesi = new LinkedHashMap<>();
  16. int maxX = 0;
  17. int maxY = 0;
  18. for (int i = 0; i < koordinatSayisi; i ++) {
  19. ArrayList<String> raf = getListFromStrSeperatedBy(in.nextLine(), " ", true);
  20. koordinatListesi.put(Integer.parseInt(raf.get(0)), Integer.parseInt(raf.get(1)));
  21. if (Integer.parseInt(raf.get(0)) > maxX) {
  22. maxX = Integer.parseInt(raf.get(0));
  23. }
  24. if (Integer.parseInt(raf.get(1)) > maxY) {
  25. maxY = Integer.parseInt(raf.get(1));
  26. }
  27. }
  28. in.close();
  29. int[][] koordinatlar = new int[maxX + 1][maxY + 1];
  30. boolean first = true;
  31. for (Entry<Integer, Integer> entry: koordinatListesi.entrySet()) {
  32. if (first) {
  33. koordinatlar[entry.getKey()][entry.getValue()] = 3;
  34. } else {
  35. koordinatlar[entry.getKey()][entry.getValue()] = 1;
  36. }
  37. }
  38. CoordinateList list = new CoordinateList();
  39. for (Entry<Integer, Integer> entry: koordinatListesi.entrySet()) {
  40. double distanceFromOrigin = Math.sqrt((double) Math.pow(entry.getValue(), 2.0) + (double)Math.pow(entry.getKey(), 2.0));
  41. list.addCoordinate(new Coordinate(entry.getKey(), entry.getValue(), distanceFromOrigin));
  42. }
  43. list.sortList();
  44. koordinatListesi = new LinkedHashMap<>();
  45. for (int i = 0; i < list.getSize(); i++) {
  46. koordinatListesi.put(list.getCoordinate(i).getX(), list.getCoordinate(i).getY());
  47. }
  48. int toplamAlan = 0;
  49. while (!checkIfDone(koordinatlar)) {
  50. for (Entry<Integer, Integer> entry: koordinatListesi.entrySet()) {
  51. list = new CoordinateList();
  52. for (Entry<Integer, Integer> entry2: koordinatListesi.entrySet()) {
  53. if (entry.equals(entry2)) {
  54. continue;
  55. }
  56. double alan = (double) Math.abs(entry2.getValue() - entry.getValue()) * (double) Math.abs(entry2.getKey() - entry.getKey());
  57. list.addCoordinate(new Coordinate(entry2.getKey(), entry2.getValue(), alan));
  58. }
  59. list.sortList();
  60. for (int i = 0; i < list.getSize(); i++) {
  61. boolean cakisma = false;
  62. Coordinate end = list.getCoordinate(i);
  63. int startX = entry.getKey();
  64. int startY = entry.getValue();
  65. int endX = end.getX();
  66. int endY = end.getY();
  67. if (endX < startX) {
  68. int temp = endX;
  69. startX = endX;
  70. endX = temp;
  71. }
  72. if (endY < startY) {
  73. int temp = endY;
  74. startY = endY;
  75. endY = temp;
  76. }
  77. if (koordinatlar[entry.getKey()][entry.getValue()] == 2 && koordinatlar[end.getX()][end.getY()] == 2
  78. || koordinatlar[entry.getKey()][entry.getValue()] == 3 && koordinatlar[end.getX()][end.getY()] == 2
  79. || koordinatlar[entry.getKey()][entry.getValue()] == 2 && koordinatlar[end.getX()][end.getY()] == 3
  80. || koordinatlar[entry.getKey()][entry.getValue()] == 3 && koordinatlar[end.getX()][end.getY()] == 3) {
  81. continue;
  82. }
  83. for (int a = startX + 1; a < endX; a++) {
  84. for (int b = startY + 1; b < endY; b++) {
  85. if (koordinatListesi.containsKey(a) && koordinatListesi.get(a).equals(b)) {
  86. cakisma = true;
  87. break;
  88. }
  89. }
  90. if (cakisma) {
  91. break;
  92. }
  93. }
  94. if (!cakisma) {
  95. System.out.println("(" + entry.getKey() + ", " + entry.getValue() + ") Eslesme (" + end.getX() + ", " + end.getY() + "): " + list.getCoordinate(i).getArea());
  96. toplamAlan += list.getCoordinate(i).getArea();
  97. if (koordinatlar[entry.getKey()][entry.getValue()] == 3 || koordinatlar[end.getX()][end.getY()] == 3) {
  98. koordinatlar[entry.getKey()][entry.getValue()] = 3;
  99. koordinatlar[end.getX()][end.getY()] = 3;
  100. }
  101. koordinatlar[entry.getKey()][entry.getValue()] = 2;
  102. koordinatlar[end.getX()][end.getY()] = 2;
  103. break;
  104. }
  105. }
  106. }
  107. }
  108. HashMap<Integer, Integer> unfinished;
  109. while ((unfinished = checkIfConnected(koordinatlar)) != null) {
  110.  
  111. }
  112. System.out.println(toplamAlan);
  113. }
  114.  
  115. public static boolean checkIfDone(int[][] koordinatlar) {
  116. boolean done = true;
  117. for (int i = 0; i < koordinatlar.length; i++) {
  118. for (int j = 0; j < koordinatlar[i].length; j++) {
  119. if (koordinatlar[i][j] == 1) {
  120. done = false;
  121. break;
  122. }
  123. }
  124. if (!done) {
  125. break;
  126. }
  127. }
  128. return done;
  129. }
  130.  
  131. public static HashMap<Integer, Integer> checkIfConnected(int[][] koordinatlar) {
  132. boolean done = true;
  133. HashMap<Integer, Integer> list = new HashMap<Integer, Integer>();
  134. for (int i = 0; i < koordinatlar.length; i++) {
  135. for (int j = 0; j < koordinatlar[i].length; j++) {
  136. if (koordinatlar[i][j] == 2) {
  137. done = false;
  138. list.put(i, j);
  139. }
  140. }
  141. }
  142. if (done) {
  143. return null;
  144. }
  145. return list;
  146. }
  147.  
  148. public static ArrayList<String> getListFromStrSeperatedBy(String str, String seperate, boolean trimResult) {
  149. ArrayList<String> list = new ArrayList<>();
  150. while (str.length() > 0) {
  151. if (str.contains(seperate)) {
  152. if (trimResult) {
  153. list.add(str.substring(0, str.indexOf(seperate)).trim());
  154. } else {
  155. list.add(str.substring(0, str.indexOf(seperate)));
  156. }
  157. str = str.substring(str.indexOf(seperate) + seperate.length());
  158. while (str.indexOf(seperate) == 0) {
  159. str = str.substring(str.indexOf(seperate) + seperate.length());
  160. }
  161. } else {
  162. if (trimResult) {
  163. list.add(str.trim());
  164. }
  165. str = "";
  166. }
  167. }
  168. return list;
  169. }
  170.  
  171. public static class Coordinate{
  172. int x;
  173. int y;
  174. double area;
  175.  
  176. public Coordinate(int x, int y, double area) {
  177. this.x = x;
  178. this.y = y;
  179. this.area = area;
  180. }
  181. public int getX() {
  182. return x;
  183. }
  184. public int getY() {
  185. return y;
  186. }
  187. public double getArea() {
  188. return area;
  189. }
  190. }
  191.  
  192. public static class CoordinateList{
  193. ArrayList<Coordinate> coordinates;
  194.  
  195. public CoordinateList() {
  196. coordinates = new ArrayList<>();
  197. }
  198. public void addCoordinate(Coordinate co) {
  199. coordinates.add(co);
  200. }
  201. public Coordinate getCoordinate(int index) {
  202. return coordinates.get(index);
  203. }
  204. public int getSize() {
  205. return coordinates.size();
  206. }
  207. public void sortList() {
  208. Collections.sort(coordinates, new Comparator<Coordinate>() {
  209. public int compare(Coordinate c1, Coordinate c2) {
  210. if (c1.getArea() == c2.getArea()) {
  211. return 0;
  212. } else if (c1.getArea() > c2.getArea()) {
  213. return 1;
  214. } else {
  215. return -1;
  216. }
  217. }
  218. });
  219. }
  220. }
  221.  
  222. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement