Форум программистов, компьютерный форум CyberForum.ru

Треугольники - C++

Восстановить пароль Регистрация
 
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
29.08.2011, 21:04     Треугольники #1
На плоскости задано n точек с целочисленными координатами. Никакие три точки не лежат на одной прямой. Определить k - количество треугольников с вершинами в заданных точках и целочисленной площадью.

Технические условия
Входные данные

В первой строке содержится число n. В последующих n строках содержаться пары целых чисел - координаты очередной точки (xi, yi). Известно, что 0 < n, |xi|,|yi| ≤ 5000.
Выходные данные

Искомое число k.

Лимит времени: 0.1 секунды

Пример
Пример входных данных
5
2 -1
3 0
0 4
-3 0
-2 1
Пример выходных данных
6

Вот мой код:
C++
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
#include <iostream>
using namespace std;
 
int xyn2k( int *x, int *y, int N );
int main()
{
int *x,*y,n,i;
scanf("%d",&n);
x=(int*)malloc(n*sizeof(int));
y=(int*)malloc(n*sizeof(int));
for (i=0; i<n; i++) scanf("%d%d",&x[i],&y[i]);
printf("%d\n",xyn2k(x,y,n));
return 0;
}
 
int xyn2k( int *x, int *y, int N )
{
int K = 0;
for( int i = 0; i < N - 2; i++ )
for( int j = i + 1; j < N - 1; j++ )
 {
  int dx = x[ i ] ^ x[ j ], dy = y[ i ] ^ y[ j ];
  for( int k = j + 1; k < N; k++ )
  K += !( ( ( y[ i ] ^ y[ k ] ) & dx ^ dy & ( x[ i ] ^ x[ k ] ) ) & 1 );
 }
return K;
}
TL На последних тестах, как можно быстрее написть это?

Добавлено через 2 часа 7 минут
Вот другая реализация. Тоже тайм лимит...

C++
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
#include <iostream>
#include <cmath>
using namespace std;
 
struct pt {
    int x,y;
};
 
int xyn2k(pt *a,int n);
int sqre(pt a, pt b, pt c);
int main()
{
 pt *a;
 int n,i;
 scanf("%d",&n);
 a=(pt*)malloc(n*sizeof(pt));
 for (i=0; i<n; i++) scanf("%d%d",&a[i].x,&a[i].y);
 printf("%d\n",xyn2k(a,n));
 return 0;
}
 
int xyn2k(pt *a,int n)
{
 int res=0,i,j,k;
 for (i=0; i<n; i++)
 for (j=i+1; j<n; j++)
 for (k=j+1; k<n; k++)
 if (!(abs(sqre(a[i],a[j],a[k]))&1)) res++;
 return res;
}
 
int sqre(pt a, pt b, pt c)
{
 return a.x*b.y+b.x*c.y+c.x*a.y-a.y*b.x-b.y*c.x-c.y*a.x;
}
Добавлено через 6 часов 18 минут
Нарооооод, есть тут кто?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.08.2011, 21:04     Треугольники
Посмотрите здесь:

C++ треугольники
C++ Процедуры. Треугольники
C++ Треугольники (C\C++)
Треугольники C++
C++ Треугольники
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
31.08.2011, 15:58     Треугольники #2
AvengerAlive, Попробуйте так:
C++
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
#include <iostream>
using namespace std;
int main()
 {
int *x,*y,n,i,j, c_c=0, c_n=0, n_c=0, n_n=0;
long long col=0;
 scanf("%d",&n);
 x=(int*)malloc(n*sizeof(int));
 y=(int*)malloc(n*sizeof(int));
 for (i=0; i<n; i++){
     scanf("%d%d",&x[i],&y[i]);
     if(x[i] & 1)
     {
         if(y[i] & 1)
             n_n++;
         else
             n_c++;
     }
     else
     {
         if(y[i] & 1)
             c_n++;
         else
             c_c++;
     }
 }
 if(c_c>1)
 {
     for(i=0; i<c_c-1; i++)
         for(j=i+1; j<c_c; j++)
             col+=(long long)(n-j-1);
 }
 if(c_n>1)
 {
     for(i=0; i<c_n-1; i++)
         for(j=i+1; j<c_n; j++)
             col+=(long long)(n-j-1);
 }
 if(n_c>1)
 {
     for(i=0; i<n_c-1; i++)
         for(j=i+1; j<n_c; j++)
             col+=(long long)(n-j-1);
 }
 if(n_n>1)
 {
     for(i=0; i<n_n-1; i++)
         for(j=i+1; j<n_n; j++)
             col+=(long long)(n-j-1);
 }
 
 
 printf("%lld\n",col);
return 0;
 }
Overmind024
99 / 99 / 6
Регистрация: 10.09.2010
Сообщений: 267
31.08.2011, 18:51     Треугольники #3
C++
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
#include <iostream>
 
using namespace std;
 
struct point {
    int x,y;
};
 
inline istream& operator>>(istream& stream, point& p)
{
    return stream >> p.x >> p.y;
}
 
size_t nod(size_t n,size_t m)
{
    while(n && m)
    {
        if(n > m)
        {
            n %= m;
        }
        else
        {
            m %= n;
        }
    }
 
    return (n+m);
}
 
inline size_t in_border(point& first,point& second)
{
    return nod(abs(first.x - second.x),abs(first.y - second.y));
}
 
inline bool whole_area(point& first,point& second,point& third)
{
    return !( (in_border(first,second) + in_border(second,third) + in_border(third,first)) % 2);
}
 
int main()
{
    size_t n, 
        k = 0;
    cin >> n;
 
    point* array = new point[n];
    for(size_t i=0;i<n;++i)
    {
        cin >> array[i];
    }
 
    for(size_t i=0;i<n;++i)
    {
        for(size_t j = i+1;j<n;++j)
        {
            for(size_t l = j+1;l<n;++l)
            {
                if (whole_area(array[i],array[j],array[l])) k++;
            }
        }
    }
 
    cout << k << endl;
 
    return 0;
}
Алгоритм основан на Формула Пика.

Добавлено через 2 часа 0 минут
C++
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
#include <stdio.h>
 
using namespace std;
 
struct point {
    int x,y;
};
 
#define MAX_SIZE 50
#define parity(n,m) (!((array[n].x - array[m].x) & 1) && !((array[n].y - array[m].y) & 1))
 
int main()
{
    size_t n, 
        k = 0;
    scanf("%d",&n);
 
    point array[MAX_SIZE];
    for(size_t i=0;i<n;++i)
    {
        scanf("%d %d",&array[i].x , &array[i].y);
    }
 
    for(size_t i=0;i<n;++i)
    {
        for(size_t j = i+1;j<n;++j)
        {
            for(size_t l = j+1;l<n;++l)
            {
                if (parity(i,j) == parity(j,l) == parity(i,l)) k++;
            }
        }
    }
 
    printf("%d\n",k);
 
    return 0;
}
Проходит 11 тестов.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
02.09.2011, 15:47  [ТС]     Треугольники #4
Да собственно моё решение тоже проходит 11 тестов...

Добавлено через 21 час 15 минут
valeriikozlov, 3 теста неверный ответ(
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.09.2011, 01:45     Треугольники #5
Цитата Сообщение от AvengerAlive Посмотреть сообщение
valeriikozlov, 3 теста неверный ответ(
А у меня все тесты прошло (на e-olimp.com). Последние 3 теста - это когда результат не вмещается в int (вычислил экспериментальным путем).
На одном из других сайтов недавно столкнулся, что там неработает спецификатор "%lld" для значений которые не вмещаются в int.
Попробуйте тогда заменить в моем коде строчку:

Цитата Сообщение от valeriikozlov Посмотреть сообщение
printf("%lld\n",col);
На:
C++
1
cout<<col;
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
03.09.2011, 13:43  [ТС]     Треугольники #6
спс, догадался)

Добавлено через 11 минут
А ты не в курсе в чём фича в задачке 32? Когда ничья или победа чёрных ответ выдаёт правильно, а вот при победе белых 15 тестов не проходит...Было у тебя такое? 90.3% проходит...
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.09.2011, 14:58     Треугольники #7
AvengerAlive, У меня задачка 32 была решена раньше. И есть вариант, когда проходило 90.3%.
В этом варианте я не учитывал:
Если конь сумел побить пешку или ферзя, то выигрывают черные
- когда конь сумел побить ферзя. Но не факт что у Вас именно из-за этого не проходит. Если нужно могу скинуть код, который прошел все тесты.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
03.09.2011, 16:35  [ТС]     Треугольники #8
У меня как раз те тесты и не проходит, что у Вас 30,31,61,112-119,127,137,143. Но на эти тесты же ответ 1, то есть выигрывает пешка. У меня учитывается что конь бьёт ферзя. Если конь бьёт ферзя то ответ -1. Разве не так?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.09.2011, 16:46     Треугольники #9
Цитата Сообщение от AvengerAlive Посмотреть сообщение
Если конь бьёт ферзя то ответ -1. Разве не так?
Да все правильно.
Можете показать свой код, я найду в нем ошибку.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
03.09.2011, 16:59  [ТС]     Треугольники #10
Вот, тут правда есть отладочная печать, можно не обращать внимания)

C++
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <cstdlib>
using namespace std;
 
int mas[12][12];
int a,b,c,d,k=0;
bool two=false;
bool kill=false;
 
int peshka();
int horse();
int horseway(int i, int j);
int main()
{
 int i,t;
 char ch;
 memset(mas,0,sizeof(mas));
 //for (i=2; i<10; i++) { for (int j=2; j<10; j++) cout << mas[i][j] << " "; cout << endl; } cout << endl << endl;
 cin >> ch >> b;
 a=ch-95; b++;
 mas[a][b]=1;
 cin >> ch >> d;
 c=ch-95; d++;
 mas[c][d]=2;
 //for (i=2; i<10; i++) { for (int j=2; j<10; j++) cout << mas[i][j] << " "; cout << endl; } cout << endl << endl;
 while (true)
  {
   //cout << "* * * WHITE * * *" << endl;
   t=peshka();
   //for (i=2; i<10; i++) { for (int j=2; j<10; j++) cout << mas[i][j] << " "; cout << endl; } cout << endl << endl;
   if (!t) { cout << "0.5" << endl; return 0; }
   if (t==-1) { cout << "1" << endl; return 0; }
   for (i=0; i<12; i++) mas[0][i]=mas[1][i]=mas[10][i]=mas[11][i]=mas[i][0]=mas[i][1]=mas[i][10]=mas[i][11]=0; 
   //cout << "* * * BLACK * * *" << endl;
   t=horse();
   //for (i=2; i<10; i++) { for (int j=2; j<10; j++) cout << mas[i][j] << " "; cout << endl; } cout << endl << endl;
   if (t==1) { cout << "-1" << endl; return 0; }
   for (i=0; i<12; i++) mas[0][i]=mas[1][i]=mas[10][i]=mas[11][i]=mas[i][0]=mas[i][1]=mas[i][10]=mas[i][11]=0;   
  }
 return 0;
}
 
int peshka()
{
 if (b==9) return -1;
 if (two && b==8) return -1;
 if (b==3)
  {
   if (!mas[a][b+1]) mas[a][b+1]=1;
   else return 0;
   if (!mas[a][b+2])
    {
     mas[a][b+2]=1;
     two=true;
    }
  }
 else
  {
   if (!two)
    {
     if (!mas[a][b+1]) mas[a][b+1]=1;
     else return 0;
    }
   else
    {
     if (mas[a][b+1]==2) return 0;
     if (!mas[a][b+2]) mas[a][b+2]=1;
     else two=false;
     if (b==8)
      {
       mas[a][10]=0;
       two=false;
      }
    }   
  }
 mas[a][b]=0;
 b++;
 return 1;
}
 
int horse()
{
 int i,j;
 if (k==1) kill=false;
 if (kill) k=1;
 for (i=2; i<10; i++)
 for (j=2; j<10; j++)
  {
   if (mas[i][j]==2 || mas[i][j]==4)
    {
     if (horseway(i+1,j+2)) return 1;
     if (horseway(i+1,j-2)) return 1;
     if (horseway(i-1,j+2)) return 1;
     if (horseway(i-1,j-2)) return 1;
     if (horseway(i+2,j+1)) return 1;
     if (horseway(i+2,j-1)) return 1;
     if (horseway(i-2,j+1)) return 1;
     if (horseway(i-2,j-1)) return 1;
     if (mas[i][j]==2) mas[i][j]=0;
    }
  }
 for (i=2; i<10; i++)
 for (j=2; j<10; j++)
  {
   if (mas[i][j]==3 || mas[i][j]==4) mas[i][j]=2;
  }
 return 0;
}
 
int horseway(int i, int j)
{
 if (!mas[i][j] || mas[i][j]==3) mas[i][j]=3;
 else if (mas[i][j]==2) mas[i][j]=4;
 else
  {
   if (!two && !kill) return 1;
   else 
    {
     mas[i][j]=3;
     if (mas[a][b]!=1) b++;
     two=false;
     kill=true;
    }
  }
 return 0;
}
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.09.2011, 17:19     Треугольники #11
В общем я нашел пробел в Вашем коде. Вот тест: g5 f6
У Вас выдает: -1. А нужно: 1.
Ведь на первом же ходе пешка бьет коня.
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
03.09.2011, 17:25  [ТС]     Треугольники #12
Вкратце чтобы не запутаться в прогу могу объяснить идею. Взял поле 12 на 12 чтоб коню было легко. 0,1,10,11 резервы для коня и обнулены. После каждого хода я на всякий случай их занового зануляю. Теперь если пешка ходит. Следующая клетка 1, та на которой стояла 0. Если пешка стартует со второй клетки доски, тут это клетка 3, идём двумя пешками. Конь так же есть 8 вариантов. Если конь берёт пешку или перекрывает то ничья. Если было 2 пешки и конь взял 1 то two=false, ид1м к случаю 1 пешки. Запущено конечно всё...

Добавлено через 44 секунды
valeriikozlov, спасибо, вот то что пешка бьёт коня я не учёл.

Добавлено через 3 минуты
Засчитано 96.5%
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.09.2011, 17:27     Треугольники #13
давайте последний вариант кода
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
03.09.2011, 17:29  [ТС]     Треугольники #14
Засчитано)

Добавлено через 22 секунды
спасибо)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.09.2011, 17:30     Треугольники
Еще ссылки по теме:

C++ Треугольники из спичек
C++ Круги и треугольники
треугольники в с++ с void C++

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.09.2011, 17:30     Треугольники #15
не за что )
Yandex
Объявления
03.09.2011, 17:30     Треугольники
Ответ Создать тему
Опции темы

Текущее время: 02:29. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru