import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Collections; import java.util.HashMap; import java.util.Map; import java.util.Map.Entry; import java.util.PriorityQueue; import java.util.Scanner; public class Solution { // public static Map<Integer, Sheet> sheets = new HashMap<Integer, Sheet>(); public static Map<String, Integer> board = new HashMap<String, Integer>();
public static PriorityQueue<Item> smallQ; public static PriorityQueue<Item> bigQ;
private static int T; private static int N;
public static void main(String[] args) { long totalTime = System.currentTimeMillis(); try { System.setIn(new FileInputStream("res/inputPaint.txt")); } catch (FileNotFoundException e) { e.printStackTrace(); }
int x,y,s;
Scanner sc = new Scanner(System.in);
T = sc.nextInt(); smallQ = new PriorityQueue<Item>();
for (int i = 0; i < T; i++) { N = sc.nextInt();
for (int j = 0; j < N; j++) { x = sc.nextInt(); y = sc.nextInt(); s = sc.nextInt(); Sheet sheet = new Sheet(x, y, s, (j+1)); sheet.doPaint(); // System.out.println(sheet); }
countColor(); bigQ = new PriorityQueue<Item>(smallQ.size(), Collections.reverseOrder()); bigQ.addAll(smallQ);
System.out.print("#"+(i+1) + " "); display(smallQ); display(bigQ);
smallQ.clear(); bigQ.clear(); board.clear(); } System.out.println("Total Time : " + (System.currentTimeMillis()-totalTime) + " ms"); }
public static void countColor() { long startTime = System.currentTimeMillis(); int color = 0; int cnt = 0; PriorityQueue<Color> pq = new PriorityQueue<Color>();
long startboard = System.currentTimeMillis(); for (Entry<String, Integer> entry : board.entrySet()) { pq.add(new Color(entry.getValue())); } System.out.println("getBoard : " + (System.currentTimeMillis() - startboard) + " ms");
long startSmall = System.currentTimeMillis(); int peek = 0; while (pq.size()>0) { peek = pq.poll().getColor(); if(color!=peek) { if(color!=0) { smallQ.add(new Item(color, cnt)); } color = peek; cnt = 1;
if(pq.size()==0) { smallQ.add(new Item(color, cnt)); } } else { cnt ++; } } System.out.println("Add smallQ : " + (System.currentTimeMillis() - startSmall) + " ms"); pq.clear(); System.out.println("CountColor : " + (System.currentTimeMillis() - startTime) + " ms"); }
private static void display(PriorityQueue<Item> pq) { long startTime = System.currentTimeMillis(); int sameCnt = 0; int val = 0; int color = 0; Item item = null; PriorityQueue<Candi> candiQ = new PriorityQueue<Candi>();
// remove zero do { item = pq.poll(); } while ((item!=null)&&(item.getCnt()==0));
// small Count do { color = item.getColor(); val = item.getCnt();
candiQ.add(new Candi(color, val)); sameCnt++;
item = pq.poll(); } while ((item!=null) && (val==item.getCnt()));
System.out.print(sameCnt + " ");
Candi candi;
while (candiQ.size()>0) { candi = candiQ.poll(); System.out.print(candi.getColor() +" " + candi.getCnt() + " "); }
System.out.println(); candiQ.clear(); System.out.println("Display : " + (System.currentTimeMillis() - startTime) + " ms"); }
} class Color implements Comparable<Color> { private int color;
public Color(int color) { this.color = color; } public int getColor() { return color; } @Override public int compareTo(Color o) { return (this.color < o.color)? -1 : 1; } /* (non-Javadoc) * @see java.lang.Object#toString() */ @Override public String toString() { return "" + color ; } } class Item implements Comparable<Item>{ private int cnt; private int color;
public Item(int color, int cnt) { this.color = color; this.cnt = cnt; }
public int getCnt() { return cnt; }
public int getColor() { return color; } @Override public int compareTo(Item o) { return (this.cnt < o.cnt) ? -1 : 1; } @Override public String toString() { return "Item [cnt=" + cnt + ", color=" + color + "]"; } }
class Candi extends Item { public Candi(int color, int cnt) { super(color, cnt); } @Override public int compareTo(Item o) { return (super.getColor() < o.getColor())? -1 : 1; } } class Sheet { private int x; private int y; private int s; private int color; private int count;
public Sheet(int x, int y, int s, int color) { this.x = x; this.y = y; this.s = s; this.color = color; }
public void doPaint() { for (int i = x; i < x+s; i++) { for (int j = y; j < y+s; j++) { String idx = convIdx(i, j); Solution.board.put(idx, color); } } // System.out.println(Solution.board); }
public void doCount() { int cnt = 0;
for (Entry<String, Integer> entry : Solution.board.entrySet()) { if(entry.getValue()==color) { cnt++; } }
count = cnt; }
public int getCount() { if(count==0) { doCount(); }
return count; }
public int getColor() { return color; }
private String convIdx(int x, int y) { return "" + x + "_" + y; } @Override public String toString() { return "Sheet [x=" + x + ", y=" + y + ", s=" + s + ", color=" + color + ", count=" + count + "]"; } } |