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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
#1

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

29.08.2011, 21:04. Просмотров 950. Ответов 14
Метки нет (Все метки)

На плоскости задано 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 минут
Нарооооод, есть тут кто?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.08.2011, 21:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Треугольники (C++):

Треугольники - C++
Интересно, можно ли на C++ (или любом другом языке) корректно определить класс треугольник, положив в его основу три хорошо известных...

Треугольники - C++
Доброй ночи\утро\день всем! Сразу прошу прощения, если такая тема уже есть - но совесть моя почти чиста - искала - и не нашла ничего...

Треугольники (C\C++) - C++
Написать программу, по длинам сторон распознающую среди всех треугольников ABC прямоугольные. Если таковых нет, то вычислить величину угла...

треугольники - C++
#include &lt;math.h&gt; #include &lt;iostream&gt; #include &quot;class.h&quot; using namespace std; tre1::tre1(double){ a=0; ...

Процедуры. Треугольники - C++
Дано два треугольника со сторонами a, b, c и d, e, f. Использовав подпрограмму, определить, являются эти треугольники прямоугольные или...

Существуют ли треугольники a, b, c, d - C++
Задали лабораторную по C++, у самой не получается сделать, не знаю даже как это реализовать, помогите пожалуйста... &quot;Даны четыре...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
valeriikozlov
Эксперт C++
4670 / 2496 / 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;
 }
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 тестов.
1
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
02.09.2011, 15:47  [ТС] #4
Да собственно моё решение тоже проходит 11 тестов...

Добавлено через 21 час 15 минут
valeriikozlov, 3 теста неверный ответ(
0
valeriikozlov
Эксперт C++
4670 / 2496 / 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;
0
AvengerAlive
5 / 5 / 0
Регистрация: 30.07.2011
Сообщений: 257
03.09.2011, 13:43  [ТС] #6
спс, догадался)

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

Добавлено через 22 секунды
спасибо)
0
valeriikozlov
Эксперт C++
4670 / 2496 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
03.09.2011, 17:30 #15
не за что )
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.09.2011, 17:30
Привет! Вот еще темы с ответами:

Перисикаются ли треугольники - C++
Здравствуйте :beach: Имеются по три вершины двух треугольников. Задача в том проверить пересекаются треугольники. Заранее спасибо! :)

Круги и треугольники - C++
http://s52.***********/i137/1406/24/eee0c48b21c0.jpg вот задания!! #include &lt;stdio.h&gt; #include &lt;conio.h&gt; #include &lt;math.h&gt; void...

треугольники в с++ с void - C++
посмотрите код.ну это для примера .все ответы нужны в таком написании Заранее спасибо Всем кто поможет void ErankyunTpel(int); ...

Треугольники из спичек - C++
Профессор Самоделкин, известный Вам по задаче &quot;Спичечная модель&quot;, решил вновь проявить свои умственные способности. Он начал складывать...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
03.09.2011, 17:30
Ответ Создать тему
Опции темы

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