Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- import java.io.BufferedReader;
- import java.awt.Point;
- public class cowrect{
- public static final String TASKNAME = "cowrect";
- public static long mod= 1000000007;
- public static Debug db;
- public static void main(String[] args) throws IOException {
- InputReader in = new InputReader(System.in);
- PrintWriter out = new PrintWriter(System.out);
- // InputReader in = new InputReader(new FileInputStream(TASKNAME+".in"));
- // PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter(TASKNAME+".out")));
- Autocompletion solver = new Autocompletion();
- db=new Debug(System.getSecurityManager()==null);
- solver.solve(1, in, out);
- out.close();
- }
- static class Autocompletion {
- public void solve(int testNumber, InputReader in, PrintWriter out) {
- int n=in.nextInt();
- Triple[] pts=new Triple[n];
- for(int i=0;i<n;i++) {
- pts[i]=new Triple(in.nextInt(),in.nextInt(),in.next().equals("H") ? 0:1);
- }
- Arrays.sort(pts);
- int ret=1;
- int area=0;
- for(int i=0;i<n;i++) {//left at point i
- if(pts[i].z==1)continue;
- int ub=Integer.MAX_VALUE;//legal portion
- int lb=Integer.MIN_VALUE;
- TreeSet<Integer> set=new TreeSet<Integer>();
- set.add(pts[i].y);
- for(int j=i+1;j<n;j++) {
- System.out.println(i+" "+j+" "+set);
- if(pts[j].z==0) {
- if(pts[j].y>=lb && pts[j].y<=ub) {
- set.add(pts[j].y);
- if(set.size()>ret) {
- ret=set.size();
- area=(set.last()-set.first())*(pts[j].x-pts[i].x);
- }
- else if(set.size()==ret) {
- area=Math.min(area, (set.last()-set.first())*(pts[j].x-pts[i].x));
- }
- }
- }
- else {
- if(pts[j].y==pts[i].y) {
- break;
- }
- else if(pts[j].y>pts[i].y) {
- if(pts[j].y<=ub) {
- ub=pts[j].y-1;
- while(!set.isEmpty() && set.last()>ub) {
- set.pollLast();
- }
- }
- }
- else {
- if(pts[j].y>=lb) {
- lb=pts[j].y+1;
- while(!set.isEmpty() && set.first()<lb) {
- set.pollFirst();
- }
- }
- }
- }
- }
- }
- out.println(ret);
- out.println(area);
- }
- }
- static class Pair implements Comparable<Pair>{
- int x;
- int y;
- Pair(int a, int b){
- x=a;
- y=b;
- }
- @Override
- public int compareTo(Pair arg0) {
- if(arg0.x!=x)return x-arg0.x;
- return y-arg0.y;
- }
- }
- static class Triple implements Comparable<Triple>{
- int x;
- int y;
- int z;
- Triple(int a, int b, int c){
- x=a;
- y=b;
- z=c;
- }
- @Override
- public int compareTo(Triple arg0) {
- if(arg0.x!=x)return x-arg0.x;
- return y-arg0.y;
- }
- }
- static class InputReader {
- public BufferedReader reader;
- public StringTokenizer tokenizer;
- public InputReader(InputStream stream) {
- reader = new BufferedReader(new InputStreamReader(stream), 32768);
- tokenizer = null;
- }
- public String next() {
- while (tokenizer == null || !tokenizer.hasMoreTokens()) {
- try {
- tokenizer = new StringTokenizer(reader.readLine());
- } catch (IOException e) {
- throw new RuntimeException(e);
- }
- }
- return tokenizer.nextToken();
- }
- public int nextInt() {
- return Integer.parseInt(next());
- }
- public long nextLong() {
- return Long.parseLong(next());
- }
- public int[] nextIntArr(int n) {
- int arr[]=new int[n];
- for(int i=0;i<n;i++) {
- arr[i]=this.nextInt();
- }
- return arr;
- }
- }
- public static class Debug {
- private boolean allowDebug;
- public Debug(boolean allowDebug) {
- this.allowDebug = allowDebug;
- }
- private void outputName(String name) {
- System.out.print(name + " = ");
- }
- public void debug(String name, int x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, long x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, double x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, int[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, long[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, double[] x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.toString(x));
- }
- public void debug(String name, Object x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println("" + x);
- }
- public void debug(String name, Object... x) {
- if (!allowDebug) {
- return;
- }
- outputName(name);
- System.out.println(Arrays.deepToString(x));
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement