ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1028. Звёзды

Some Help
Послано YoCOmo 14 май 2009 09:06
Hi
Im trying to solve this problem, here is my code

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;


public class Main{

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        try {
        //  BufferedReader in = new BufferedReader(new FileReader("stars.in"));
          BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

            int numberOfStarts = new Integer(in.readLine());

            Map<MyPoint, Integer> xOrderMap = new TreeMap<MyPoint, Integer>(new XComparator());
            Map<MyPoint, Integer> yOrderMap = new TreeMap<MyPoint,Integer>(new YComparator());
            int starIndex = 0;
            while(numberOfStarts-->0)
            {
                String strStar = in.readLine();
                StringTokenizer str = new StringTokenizer(strStar);
                MyPoint star = new MyPoint(new Integer(str.nextToken()),new Integer(str.nextToken()));
                xOrderMap.put(star,starIndex);
                yOrderMap.put(star,starIndex);
                starIndex++;
            }
            Iterator<MyPoint> xIterator = xOrderMap.keySet().iterator();
            Iterator<MyPoint> yIterator = yOrderMap.keySet().iterator();

            List<MyPoint> xList = new ArrayList<MyPoint>();
            List<MyPoint> yList = new ArrayList<MyPoint>();

            while(xIterator.hasNext())
            {
                MyPoint xPoint = xIterator.next();
                xList.add(xPoint);
            }
            while(yIterator.hasNext())
            {
                MyPoint yPoint = yIterator.next();
                yList.add(yPoint);
            }
            int  levels[] = new int[starIndex];

            for(int i = 0;i<xList.size();i++)
            {
                MyPoint point = xList.get(i);
                int yIndex = yList.indexOf(point);
                levels[yIndex<i?yIndex:i]++;
            }
            for(int i = 0;i<levels.length;i++)
            {
                out.write(levels[i]+"");
                out.newLine();
            }
            out.flush();


        } catch (Exception e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }



    }

}
class XComparator implements Comparator<Object>{

    public int compare(Object o1, Object o2) {
        // TODO Auto-generated method stub
        MyPoint p1 = (MyPoint)o1;
        MyPoint p2 = (MyPoint)o2;
        if(p1.x<p2.x)
            return -1;
        if(p1.x>p2.x)
            return 1;

        if(p1.y<p2.y)
            return -1;
        if(p1.y>p2.y)
            return 1;

        return 0;
    }

}
class YComparator implements Comparator<Object>{

    public int compare(Object o1, Object o2) {
        // TODO Auto-generated method stub
        MyPoint p1 = (MyPoint)o1;
        MyPoint p2 = (MyPoint)o2;
        if(p1.y<p2.y)
            return -1;
        if(p1.y>p2.y)
            return 1;
        if(p1.x<p2.x)
            return -1;
        if(p1.x>p2.x)
            return 1;
        return 0;
    }

}
class MyPoint
{
    int x;
    int y;
    public MyPoint(int x, int y)
    {
        this.x=x;
        this.y=y;
    }
    public String toString()
    {
        return x+","+y;
    }
}


The idea is that in xOrderMap and yOrderMap i keep ordered the stars in x or y order. For get the level of a star i just follow the description of the problem all stars to the left and below of a star are of lower level, because of that i look up the index of a star in xOrderMap and yOrderMap and all star that is to the left of a star in both maps are lower than a star. THIS CORRECT?

Can someone help me for finding the reason why my code gives WA?
Or can somenone help me with some tricky cases?
Re: Some Help
Послано gvsmirnov 18 сен 2009 21:33
You don't consider it when a star is below AND to the left. You just count such stars twice.