Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/6: Рейтинг темы: голосов - 6, средняя оценка - 4.67
49 / 49 / 13
Регистрация: 11.01.2013
Сообщений: 198
1

Задачка с acmp

30.01.2013, 13:44. Просмотров 1153. Ответов 1
Метки нет (Все метки)


задача 421 с сайта ******** [нерабочая ссылка]
не проходит 4 тест
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.*;
import java.io.*;
import java.math.*;
class Point implements Comparable<Object>
{
        double x;
        double y;
public Point ()
{
    x=0;
    y=0;
}
public void setPoint (double x , double y)
{
    this . x = x;
    this . y = y;
}
 
public double getPointX ()
{
    return this . x;
}
 
public double getPointY ()
{
    return this . y;
}
 
public int compareTo(Object obj)
{
        Point tmp = (Point)obj;
        if( this.x > tmp.x || ( this.x == tmp.x && this.y > tmp.y) )
            return 1;
        else{
        if( this.x < tmp.x || ( this.x == tmp.x && this.y < tmp.y) )
            return -1;
        
        return 0;
        }
}        
 
}
 
 
public class Main {
    
static double sqr (double a){
    return a*a;
    
}
 
public static double cross (Point O,Point A, Point B)
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
public static void main(String[] argv) throws IOException {
                  
         Scanner sc = new Scanner(new File("input.txt"));                  
         PrintWriter pw = new PrintWriter(new File("output.txt"));
         int n = sc.nextInt();
         int i , j;
         double  a [] = new double [3] , b [] = new double [3];
         Point m [] = new Point [3];
         for(i = 0; i < 3; i++) m [ i ] = new Point ();
         Point l [] = new Point [3];
         for(i = 0; i < 3; i++) l [ i ] = new Point ();
         
         
         for( i = 0; i < n ; i++ ){
             
             for(j=0;j<3;j++){
             double x =sc.nextDouble(), y=sc.nextDouble();
             m [ j ] . setPoint( x , y );}
             Arrays.sort(m);     
              
              
         a [ 0 ] =  Math.sqrt( sqr ( m [ 0 ] . x  - m [ 1 ] . x ) + sqr ( m [ 0 ] . y - m [ 1 ] . y ) );
         a [ 1 ] =  Math.sqrt( sqr ( m [ 0 ] . x  - m [ 2 ] . x ) + sqr ( m [ 0 ] . y - m [ 2 ] . y ) ); 
         a [ 2 ] =  Math.sqrt( sqr ( m [ 1 ] . x  - m [ 2 ] . x ) + sqr ( m [ 1 ] . y - m [ 2 ] . y ) );     
         Arrays.sort(a);
         
         if(i>0)
         if(a[0]==b[0]&&a[1]==b[1]&&a[2]==b[2]){}
         else { pw.print("NO");pw.close();return;}
       
         
         double aa=cross(m[0], m[1], m[2]);
         double bb=cross(l[0], l[1], l[2]);
         System.out.println(aa+" "+bb);
        
         if(i>0)
         if( (aa<=0 && bb<=0 ) || (aa>=0 && bb>=0)    ){ }
         else { pw.print("NO");pw.close();return;}
         
         b[0]=a[0];b[1]=a[1];b[2]=a[2];    
         l[0]=m[0];l[1]=m[1];l[2]=m[2];
                  
         }
         
        
            pw.print("YES");
            pw.close();
              
 
}
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
30.01.2013, 13:44
Ответы с готовыми решениями:

Задачка 435 с acmp.ru -ускорить работу кода
Вот мой код работает медленно, а так вроде бы правильный, нноо хотелось бы оптимизировать также...

Количество палиндромов (задачка с acmp.ru)
Доброго времени суток. Нужна помощь с заданием на с++. Текст задания: Количество палиндромов...

№38 с acmp.ru
Решал так. Беру массив пар dp NxN, где номер строки - число цифр, убранных с правой стороны, а...

Графы (acmp 97)
В райской долине расположены N заповедников, имеющих форму прямоугольников. Однажды на собрании...

1
49 / 49 / 13
Регистрация: 11.01.2013
Сообщений: 198
02.02.2013, 20:28  [ТС] 2
Сдал , алгоритм такой что надо отсортировать стороны всех треугольников по часовой стрелки (или против) с помощью векторного произведения и потом проверить у двух треугольников не обязательно попарно можно просто i с i+1 проверять равенство треугольников так что они должны быть равны по трем сторонам(предварительно отсортированным как сказано выше) хотя бы в одном циклическом сдвиге первого тоесть к примеру берем 2 треугольника сортируем и смотрим 3 циклические перестановки второго и сравниваем соответственно стороны первого со сторонами всех циклических перестановок второго если хотя бы одной равно то YES если ни одной не равно то NO.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.02.2013, 20:28

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Охотник acmp
Привет всем. Решаю такую задачу: Сезон охоты очень не долог, и поэтому оставшуюся часть года...

Боги (задача с acmp)
Здравствуйте. Проблема с решением задачи &quot;Боги&quot; (_http://********/?main=task&amp;id_task=93). Вот...

Задача 401 с acmp
Всем привет. Есть такая задача из категории &quot;Динамическое программирование&quot;. В динамике я всегда...

Задача с acmp. Массив
Помогите решить задачу: (http://********/index.asp?main=task&amp;id_task=711) После очередного этапа...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.