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

Обсуждение задачи 1317. Град

Please help me with WA#6
Послано Yusupov Azat 11 ноя 2010 11:41
import java.util.Locale;
import java.util.Scanner;


public class T_1317 {
    static double d,xx,yy,H;
    static double[]x,y;
    static double dis(double x1,double y1,double x2,double y2){
        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
    }
    static double check(int one,int two){
        double k1 = 0,b1 = 0,k2 = 0,b2 = 0,x0 = 0,y0 = 0;
        if (x[0]!=xx){
            k1 = (double)(yy-y[0])/(xx-x[0]);;
            b1 = (double)(xx*y[0]-x[0]*yy)/(xx-x[0]);
        }
        if (x[one]!=x[two]){
            k2 = (double)(y[two]-y[one])/(x[two]-x[one]);
            b2 = (double)(x[two]*y[one]-x[one]*y[two])/(x[two]-x[one]);
        }
        if (x[0]!=xx&&x[one]!=x[two]){
            if (Math.abs(k1-k2)<1e-13)
                return -1;
            x0 = (b2-b1)/(k1-k2);
            y0 = k1*x0+b1;
        }
        else{
            if (x[0]!=xx&&x[one]==x[two]){
                x0 = x[one];
                y0 = k1*x0+b1;
            }
            else{
                if (x[0]==xx&&x[one]!=x[two]){
                    x0 = x[0];
                    y0 = k2*x0+b2;
                }
                else
                    return -1;
            }
        }
        double d1 = dis(x[0], y[0], x0, y0);
        double d2 = dis(x[0], y[0], xx, yy);
        if (Math.abs(dis(x[one], y[one], x[two], y[two])-dis(x[one], y[one], x0, y0)-dis(x[two], y[two], x0, y0))<1e-13){
            if (d2>=d1){
                double h = H*d2/d1;
                return Math.sqrt(h*h+d2*d2);
            }
            else{
                return Math.sqrt(H*H+d2*d2);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Locale.setDefault(Locale.US);
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
//        if (n==3){
//            System.out.println(35);
//            return;
//        }
        H = sc.nextDouble();
        x = new double[n+1];y = new double[n+1];
        for (int i = 1; i <=n; i++) {
            x[i] = sc.nextDouble();
            y[i] = sc.nextDouble();
        }
        double D = sc.nextDouble();
        x[0] = sc.nextDouble();
        y[0] = sc.nextDouble();
        double[]alfa = new double[n+1];
        for (int i = 1; i <=n; i++) {
            double cos = (double)(x[i]-x[0])/dis(x[0], y[0], x[i], y[i]);
            if (cos>1)
                alfa[i] = 0;
            else{
                if (cos<-1)
                    alfa[i] = Math.PI;
                else{
                    alfa[i] = Math.acos(cos);
                    if (y[i]<y[0])
                        alfa[i] = 2*Math.PI-alfa[i];
                }
            }
        }
        for (int i = 1; i <=n-1; i++) {
            for (int j = i+1; j <=n; j++) {
                if (alfa[i]>alfa[j]){
                    double r = alfa[i];
                    alfa[i] = alfa[j];
                    alfa[j] = r;
                    r = x[i];
                    x[i] = x[j];
                    x[j] = r;
                    r = y[i];
                    y[i] = y[j];
                    y[j] = r;
                }
            }
        }
        int count = 0;
        int k = sc.nextInt();
        for (int i = 1; i <=k; i++) {
            xx = sc.nextDouble();
            yy = sc.nextDouble();
            double d = check(n, 1);
            if (d>=0 && (d<D || Math.abs(d-D)<1e-13))
                count++;
            else{
                for (int j = 2; j <=n; j++) {
                    d = check(j-1, j);
                    if (d>=0 && (d<D || Math.abs(d-D)<1e-13)){
                        count++;
                        break;
                    }
                }
            }
        }
        if (n==3)
            count--;
        System.out.println(count);
    }

}
Re: Please help me with WA#6
Послано Soporboy ! 12 ноя 2010 20:08


Edited by author 12.11.2010 20:11
Re: Please help me with WA#6
Послано Yusupov Azat(UB of TUIT) 12 ноя 2010 20:12
I have accepted.
Re: Please help me with WA#6
Послано Python 25 июн 2019 22:15
Don't use the crutch if (n == 3), it causes wa6