Advertisement
Guest User

Untitled

a guest
Sep 27th, 2015
273
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.49 KB | None | 0 0
  1. package main;
  2.  
  3. import lib.InputReader;
  4. import java.io.PrintWriter;
  5. import java.util.*;
  6.  
  7. public class TaskB {
  8.     static List<Point> all = new ArrayList<>();
  9.  
  10.     static class Point {
  11.         int x;
  12.         int y;
  13.         char dir = '?';
  14.         Point prevX;
  15.         Point prevY;
  16.         Point nextX;
  17.         Point nextY;
  18.         Point savePrevX;
  19.         Point savePrevY;
  20.         Point saveNextX;
  21.         Point saveNextY;
  22.  
  23.         public Point() {
  24.             all.add(this);
  25.         }
  26.     }
  27.  
  28.     public void solve(int testNumber, InputReader in, PrintWriter out) {
  29.         int n = in.nextInt();
  30.         Point[] p = new Point[n];
  31.         for (int i = 0; i < n; ++i) {
  32.             p[i] = new Point();
  33.             p[i].x = in.nextInt();
  34.             p[i].y = in.nextInt();
  35.             p[i].dir = in.next().charAt(0);
  36.         }
  37.         Map<Integer, Point> sentinelX = new HashMap<>();
  38.         Map<Integer, Point> sentinelY = new HashMap<>();
  39.         Arrays.sort(p, new Comparator<Point>() {
  40.             @Override
  41.             public int compare(Point o1, Point o2) {
  42.                 return o1.x - o2.x;
  43.             }
  44.         });
  45.         for (Point pp : p) {
  46.             Point s = sentinelX.get(pp.y);
  47.             if (s == null) {
  48.                 s = new Point();
  49.                 s.nextX = s;
  50.                 s.prevX = s;
  51.                 sentinelX.put(pp.y, s);
  52.             }
  53.             pp.nextX = s;
  54.             pp.prevX = s.prevX;
  55.             pp.nextX.prevX = pp;
  56.             pp.prevX.nextX = pp;
  57.         }
  58.         Arrays.sort(p, new Comparator<Point>() {
  59.             @Override
  60.             public int compare(Point o1, Point o2) {
  61.                 return o1.y - o2.y;
  62.             }
  63.         });
  64.         for (Point pp : p) {
  65.             Point s = sentinelY.get(pp.x);
  66.             if (s == null) {
  67.                 s = new Point();
  68.                 s.nextY = s;
  69.                 s.prevY = s;
  70.                 sentinelY.put(pp.x, s);
  71.             }
  72.             pp.nextY = s;
  73.             pp.prevY = s.prevY;
  74.             pp.nextY.prevY = pp;
  75.             pp.prevY.nextY = pp;
  76.         }
  77.         for (Point pp : all) {
  78.             pp.savePrevX = pp.prevX;
  79.             pp.saveNextX = pp.nextX;
  80.             pp.savePrevY = pp.prevY;
  81.             pp.saveNextY = pp.nextY;
  82.         }
  83.         int res = 0;
  84.         for (int i = 0; i < n; ++i) {
  85.             for (Point pp : all) {
  86.                 pp.prevX = pp.savePrevX;
  87.                 pp.nextX = pp.saveNextX;
  88.                 pp.prevY = pp.savePrevY;
  89.                 pp.nextY = pp.saveNextY;
  90.             }
  91.             int cnt = 0;
  92.             Point at = p[i];
  93.             while (at.dir != '?') {
  94.                 ++cnt;
  95.                 at.nextX.prevX = at.prevX;
  96.                 at.prevX.nextX = at.nextX;
  97.                 at.nextY.prevY = at.prevY;
  98.                 at.prevY.nextY = at.nextY;
  99.                 switch (at.dir) {
  100.                     case '>':
  101.                         at = at.nextX;
  102.                         break;
  103.                     case '<':
  104.                         at = at.prevX;
  105.                         break;
  106.                     case '^':
  107.                         at = at.prevY;
  108.                         break;
  109.                     case 'v':
  110.                         at = at.nextY;
  111.                         break;
  112.                     default:
  113.                         throw new RuntimeException("" + at.dir);
  114.                 }
  115.             }
  116.             res = Math.max(res, cnt);
  117.         }
  118.         out.println(res);
  119.     }
  120. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement