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

Задача с вершинами квадрата - C++

Восстановить пароль Регистрация
 
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
15.01.2013, 21:49     Задача с вершинами квадрата #1
Помогите с задачей, сказали что уровень олимпиады, а нужно сдать.
Заданно множество точек на плоскости своими координатами. Выбрать среди них четыре разные точки, которые являются вершинами квадрата наибольшего периметра. Определить количество точек внутри и вне квадрата.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.01.2013, 21:49     Задача с вершинами квадрата
Посмотрите здесь:

C++ Даны целые числа. Выяснить, найдутся ли среди точек четыре таких, которые являются вершинами квадрата
C++ Являются ли точки вершинами треугольника
C++ Сравнить площадь круга и площадь квадрата , которые заданы сответствено радиусом r и стороной квадрата a
C++ Шифровать методом Магического квадрата (размер квадрата 9х9) С++
Массивы. Заполнить, разбить на квадраты размером 3х3. В центре каждого квадрата поместить сумму остальных элементов квадрата C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
15.01.2013, 22:13     Задача с вершинами квадрата #2
координаты нецелочисленные?
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
15.01.2013, 22:15  [ТС]     Задача с вершинами квадрата #3
если честно - не знаю, но думаю что можно взять и целые числа для облегчения задачи
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
15.01.2013, 22:22     Задача с вершинами квадрата #4
почему ты взялся за эту задачу, не обсудив условие? Ты ученик? Задачу учитель задал что ли? Ладно, будем считать, что целочисленные, хранятся в статическом массиве структур.
ulian
0 / 0 / 0
Регистрация: 28.11.2012
Сообщений: 53
15.01.2013, 22:25  [ТС]     Задача с вершинами квадрата #5
Именно, преподаватель задал задачу. Конечный срок - 17 число( выручайте, я понимаю что задача не легкая, но если кто-то знает - помогите
Venzo
 Аватар для Venzo
125 / 123 / 4
Регистрация: 03.07.2011
Сообщений: 354
15.01.2013, 23:24     Задача с вершинами квадрата #6
аналогичная задача, но без последнего условия
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.01.2013, 05:00     Задача с вершинами квадрата
Еще ссылки по теме:

Найти двузначные числа, у которых сумма удвоенного квадрата первой цифры и квадрата второй цифры равен самому числу C++
Площадь квадрата равна S. Вычислить сторону квадрата а, диагональ d и площадь S1 описанного около этого квадрата круга C++

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

Или воспользуйтесь поиском по форуму:
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
16.01.2013, 05:00     Задача с вершинами квадрата #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
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
#include <iostream>
using namespace std;
const int size=10;
typedef int ptype;
struct vector{
    ptype x;
    ptype y;
};
vector data[size]={{0,0}, {-4, -2}, {1,1},{0,1}, {6,3}, {3, 3},  {-2, -1}, {-5, -2}, {-4, -5}, {-1, -4}};
bool are_ortho(vector a, vector b){
   return (a.x*b.y+a.y*b.x)!=0;
}
vector norm(vector a){
    vector result={a.y, -a.x};
    return result;
}
ptype norm2(vector a){
    return (a.x*a.x+a.y*a.y);
}
vector minus(vector a, vector b){
    vector result={a.x-b.x, a.y-b.y};
    return result;
}
ptype dot_product(vector a, vector b){
    return a.x*b.x+a.y*b.y;
}
int main(){
    int inside=0, outside=0;
    bool in;
    int i, j, k, t;
    ptype a, b, c, d;
    vector ab, ad;
    vector norms[4];
    int pmax=0;
    int max[4];
    for (int i=0; i<size; i++)
        for (int j=i; j<size; j++)
            for (int k=j; k<size; k++)
                for (int t=k; t<size; t++){
                    ab=minus(data[i], data[j]);
                    ad=minus(data[t], data[i]);
                     a=norm2(ab);
                     b=norm2(minus(data[j], data[k]));
                     c=norm2(minus(data[k], data[t]));
                     d=norm2(ad);
                     if (a==b && a==c && a==d)
                         if (are_ortho(ab, ad))
                             if(pmax<a+b+c+d){
                                 pmax=a+b+c+d;
                                 max[0]=i, max[1]=j, max[2]=k, max[3]=t;
                             }
                }
cout<<"max square are points number:"<<max[0]<<" "<<max[1]<<" "<<max[2]<<" "<<max[3]<<endl;
for (int i=0; i<4; i++)
    norms[i]=norm(minus(data[max[(i==3)?0:i+1]], data[max[i]]));
for (int i=0; i<size; i++)
    if(i!=max[0]&&i!=max[1]&&i!=max[2]&&i!=max[3]){
        in=true;
        for(j=0; j<4; j++)
            in=(in&&dot_product(minus(data[i],data[max[j]]), norms[j])<0);
        if (in) inside++;
    }
outside=size-inside;
cout<<"inside: "<<inside<<"points, outside: "<<outside<<"points"<<endl;
return 0;
}
Yandex
Объявления
16.01.2013, 05:00     Задача с вершинами квадрата
Ответ Создать тему
Опции темы

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