Advertisement
ec1117

Untitled

Jun 24th, 2020
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.63 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3. import java.io.BufferedReader;
  4. import java.awt.Point;
  5.  
  6. public class cowrect{
  7. public static final String TASKNAME = "cowrect";
  8. public static long mod= 1000000007;
  9. public static Debug db;
  10.  
  11. public static void main(String[] args) throws IOException {
  12. InputReader in = new InputReader(System.in);
  13. PrintWriter out = new PrintWriter(System.out);
  14. // InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
  15. // PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
  16. Autocompletion solver = new Autocompletion();
  17. db=new Debug(System.getSecurityManager()==null);
  18. solver.solve(1, in, out);
  19. out.close();
  20. }
  21. static class Autocompletion {
  22.  
  23. public void solve(int testNumber, InputReader in, PrintWriter out) {
  24. int n=in.nextInt();
  25. Triple[] pts=new Triple[n];
  26. for(int i=0;i<n;i++) {
  27. pts[i]=new Triple(in.nextInt(),in.nextInt(),in.next().equals("H") ? 0:1);
  28. }
  29. Arrays.sort(pts);
  30. int ret=1;
  31. int area=0;
  32. for(int i=0;i<n;i++) {//left at point i
  33. if(pts[i].z==1)continue;
  34. int ub=Integer.MAX_VALUE;//legal portion
  35. int lb=Integer.MIN_VALUE;
  36. TreeSet<Integer> set=new TreeSet<Integer>();
  37. set.add(pts[i].y);
  38. for(int j=i+1;j<n;j++) {
  39. System.out.println(i+" "+j+" "+set);
  40. if(pts[j].z==0) {
  41. if(pts[j].y>=lb && pts[j].y<=ub) {
  42. set.add(pts[j].y);
  43. if(set.size()>ret) {
  44. ret=set.size();
  45. area=(set.last()-set.first())*(pts[j].x-pts[i].x);
  46. }
  47. else if(set.size()==ret) {
  48. area=Math.min(area, (set.last()-set.first())*(pts[j].x-pts[i].x));
  49. }
  50. }
  51. }
  52. else {
  53. if(pts[j].y==pts[i].y) {
  54. break;
  55. }
  56. else if(pts[j].y>pts[i].y) {
  57. if(pts[j].y<=ub) {
  58. ub=pts[j].y-1;
  59. while(!set.isEmpty() && set.last()>ub) {
  60. set.pollLast();
  61. }
  62. }
  63. }
  64. else {
  65. if(pts[j].y>=lb) {
  66. lb=pts[j].y+1;
  67. while(!set.isEmpty() && set.first()<lb) {
  68. set.pollFirst();
  69. }
  70. }
  71. }
  72. }
  73. }
  74. }
  75. out.println(ret);
  76. out.println(area);
  77. }
  78. }
  79.  
  80. static class Pair implements Comparable<Pair>{
  81. int x;
  82. int y;
  83. Pair(int a, int b){
  84. x=a;
  85. y=b;
  86. }
  87. @Override
  88. public int compareTo(Pair arg0) {
  89. if(arg0.x!=x)return x-arg0.x;
  90. return y-arg0.y;
  91. }
  92. }
  93. static class Triple implements Comparable<Triple>{
  94. int x;
  95. int y;
  96. int z;
  97. Triple(int a, int b, int c){
  98. x=a;
  99. y=b;
  100. z=c;
  101. }
  102. @Override
  103. public int compareTo(Triple arg0) {
  104. if(arg0.x!=x)return x-arg0.x;
  105. return y-arg0.y;
  106. }
  107. }
  108.  
  109. static class InputReader {
  110. public BufferedReader reader;
  111. public StringTokenizer tokenizer;
  112.  
  113. public InputReader(InputStream stream) {
  114. reader = new BufferedReader(new InputStreamReader(stream), 32768);
  115. tokenizer = null;
  116. }
  117.  
  118. public String next() {
  119. while (tokenizer == null || !tokenizer.hasMoreTokens()) {
  120. try {
  121. tokenizer = new StringTokenizer(reader.readLine());
  122. } catch (IOException e) {
  123. throw new RuntimeException(e);
  124. }
  125. }
  126. return tokenizer.nextToken();
  127. }
  128.  
  129. public int nextInt() {
  130. return Integer.parseInt(next());
  131. }
  132. public long nextLong() {
  133. return Long.parseLong(next());
  134. }
  135. public int[] nextIntArr(int n) {
  136. int arr[]=new int[n];
  137. for(int i=0;i<n;i++) {
  138. arr[i]=this.nextInt();
  139. }
  140. return arr;
  141. }
  142. }
  143. public static class Debug {
  144. private boolean allowDebug;
  145.  
  146. public Debug(boolean allowDebug) {
  147. this.allowDebug = allowDebug;
  148. }
  149.  
  150. private void outputName(String name) {
  151. System.out.print(name + " = ");
  152. }
  153.  
  154. public void debug(String name, int x) {
  155. if (!allowDebug) {
  156. return;
  157. }
  158.  
  159. outputName(name);
  160. System.out.println("" + x);
  161. }
  162.  
  163. public void debug(String name, long x) {
  164. if (!allowDebug) {
  165. return;
  166. }
  167. outputName(name);
  168. System.out.println("" + x);
  169. }
  170.  
  171. public void debug(String name, double x) {
  172. if (!allowDebug) {
  173. return;
  174. }
  175. outputName(name);
  176. System.out.println("" + x);
  177. }
  178.  
  179. public void debug(String name, int[] x) {
  180. if (!allowDebug) {
  181. return;
  182. }
  183. outputName(name);
  184. System.out.println(Arrays.toString(x));
  185. }
  186.  
  187. public void debug(String name, long[] x) {
  188. if (!allowDebug) {
  189. return;
  190. }
  191. outputName(name);
  192. System.out.println(Arrays.toString(x));
  193. }
  194.  
  195. public void debug(String name, double[] x) {
  196. if (!allowDebug) {
  197. return;
  198. }
  199. outputName(name);
  200. System.out.println(Arrays.toString(x));
  201. }
  202.  
  203. public void debug(String name, Object x) {
  204. if (!allowDebug) {
  205. return;
  206. }
  207. outputName(name);
  208. System.out.println("" + x);
  209. }
  210.  
  211. public void debug(String name, Object... x) {
  212. if (!allowDebug) {
  213. return;
  214. }
  215. outputName(name);
  216. System.out.println(Arrays.deepToString(x));
  217. }
  218. }
  219. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement