fentg.com

ФОРУМЪТ на ФЕНОВЕТЕ на НТГ
Дата и час: Нед Апр 11, 2021 8:02 am

Часовете са според зоната UTC + 2 часа [ DST ]


Правила на форума


Натиснете за да видите правилата



Напиши нова тема Отговори на тема  [ 17 мнения ]  Отиди на страница Предишна  1, 2
Автор Съобщение
 Заглавие: Re: Архив със задачи
МнениеПубликувано на: Чет Яну 22, 2009 10:07 pm 
Offline

Регистриран на: Сря Ное 19, 2008 5:48 pm
Мнения: 513
Задача с която се проверява дали точка е в триъгълник по дадени координати на 4-те точки.
Когато точката лежи на някоя от страните на триъгълника изписва, че е вътре според мен така и трябва.
За да си представя по лесно как действа програмата си представям, че триъгълникът е права и когато точката е извън тази точка се образува триъгълник и по теоремата 2-те страни са по дълги от 1-та. Начертано е по лесно за разбиране.

Цитат:
#include<stdio.h>
#include<conio.h>
#include<math.h>
void main(void)
{ float ax, ay, bx, by, cx, cy, dx, dy ;
float a, b, c, ad, bd, cd ;


printf("Enter Ax: "); scanf("%f",&ax);

printf("Enter Ay: "); scanf("%f",&ay);

printf("Enter Bx: "); scanf("%f",&bx);

printf("Enter By: ");scanf("%f",&by);

printf("Enter Cx: "); scanf("%f",&cx);

printf("Enter Cy: "); scanf("%f",&cy);

printf("Enter Dx: "); scanf("%f",&dx);

printf("Enter Dy: "); scanf("%f",&dy);


c=abs(((by-ay)*(bx-ax))/2);
b=abs(((cy-ay)*(cx-ax))/2);
a=abs(((by-cy)*(bx-cx))/2);
ad=abs(((dy-ay)*(dx-ax))/2);
bd=abs(((by-dy)*(bx-dx))/2);
cd=abs(((cy-dy)*(cx-dx))/2);

if(ad+bd==b+a||bd+cd==c+b||ad+cd==a+c)
printf("na raba");
else if(ad+bd>b+a||bd+cd>c+b||ad+cd>a+c)
printf("d e izvan triagalnik abc");
else printf ("d e v triagalnik abc");

getch();

}

_________________
Toва което не може да се опише с думи, се описва с музика.


Последна промяна mitko на Чет Яну 22, 2009 11:07 pm, променена общо 1 път

Върнете се в началото
 Профил  
 
 Заглавие: Re: Архив със задачи
МнениеПубликувано на: Чет Яну 22, 2009 10:43 pm 
Offline
Администратор
Аватар

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
Ами май лесно може да се отшлайфа - ако точката лежи на страна да съобщава - "на ръба", иначе "вън" или "вътре".

Ще ни го поначертаеш утре да се досетим...

_________________
Изображение


Върнете се в началото
 Профил  
 
 Заглавие: Re: Архив със задачи
МнениеПубликувано на: Чет Яну 22, 2009 11:09 pm 
Offline

Регистриран на: Сря Ное 19, 2008 5:48 pm
Мнения: 513
Поправих горната програма с това "на ръба" за да не пускам излишни сорсове, пробвах го с успоредна на абцисата за да може да съм сигурен, че е на ръба и всичко е ток, съмнява ме, че има някоя теорема дори.

_________________
Toва което не може да се опише с думи, се описва с музика.


Върнете се в началото
 Профил  
 
 Заглавие: Re: Архив със задачи
МнениеПубликувано на: Пет Яну 23, 2009 8:41 pm 
Offline

Регистриран на: Сря Ное 19, 2008 5:48 pm
Мнения: 513
Програмата изгърмя и то на няколко пъти, на триъгълници подобни на онзи с който ми дадохте да пробвам да обясня как става.. но сега става интересно, защото някой път става а друг път не и ми е чудно кога става и кога не и защо.

_________________
Toва което не може да се опише с думи, се описва с музика.


Върнете се в началото
 Профил  
 
 Заглавие: Re: Архив със задачи
МнениеПубликувано на: Пет Яну 23, 2009 9:43 pm 
Offline
Администратор
Аватар

Регистриран на: Нед Ное 02, 2008 5:30 pm
Мнения: 3550
Ми айде да те видим сега... :thumbsup:

_________________
Изображение


Върнете се в началото
 Профил  
 
 Заглавие: Re: Архив със задачи
МнениеПубликувано на: Пон Фев 25, 2013 2:41 am 
Offline

Регистриран на: Сря Ное 19, 2008 5:48 pm
Мнения: 513
Сега се сещам, за едно хитро решение, с което бих могъл и с тогавашните си знания да реша задачата :D Просто се пресмята лицето на триъгълник ABC и ако то е равно на сбора от лицата на трите триъгълника, ABD ACD BCD то точка D е вътре в триъгълника, в противен случай точката е извън триъгълника :D със сигурност не е най-икономичното решение, но сега чак ме хваща яд, че тогава не съм се сетил за това решение :D

_________________
Toва което не може да се опише с думи, се описва с музика.


Върнете се в началото
 Профил  
 
 Заглавие: Re: Архив със задачи
МнениеПубликувано на: Нед Юни 07, 2015 3:02 am 
Offline

Регистриран на: Чет Авг 06, 2009 3:11 am
Мнения: 21
Една много яка задача от мен :
Дадени са n точки в равнината, зададени с координатите си. Да се намери изпъкнал многоъгълник с минимално лице (минимално изпъкнало множество), който ги съдържа. Изискват се само кординатите на точките да извади.

Така ще дам на готово и два алгорима които намерих :laught: :laught:

Алгоритъм :
1. Избираме от множеството точки тази, която има най-малка X координата. Aко
има няколко такива, избираме тази с най-малка Y координата. Нека тази точка
е S. S със сигурност е от обвивката.
2. Взимаме произволна точка от останалите (нека тази точка е Т).
3. Обхождаме останалите точки Pi и ако текущата точка е от дясно на правата
ST, Pi става Т (T:=Pi).
4. Така намерената права ST е от обвивката, защото от дясно на нея няма други
точки.
5. Повтаряме стъпки 1-4, като този път избора на S е различен - избираме за S
последно намереното Т.
6. Алгоритъмът продължава докато не получим затворен полигон т.е. Т съвпадне
с първоначално избраната точка S, тъй като намерените точки от обвивката
са в порядъка, в който се срещат по изпъкналия полигон.
Сложността на алгоритъма е O(n2), където n е броят на точките.

Това е първия който аз реализирах :D

За втория ще кажа само името му - Graham Scan

Предлагам едно мое решение:
Код:
#include <stdlib.h>
#include <stdio.h>

typedef struct {
   int positionX;
   int positionY;
   int selectedPoint;
} coortinatPoint;

/*
This function insert point in Array
*/
void insertCoortinatesOfPoints(coortinatPoint *points, int numberOfPoints);
/*
This function print convex hull
*/
void printConvexHull(coortinatPoint *points, int numberOfPoints);
/*
This function returns the point of the little X, if X equals that with less Y
*/
int findMinXPoint(coortinatPoint *points, int numberOfPoints);
/*
   Check point is right from line ST
*/
int checkPointIsRigthFromLine(coortinatPoint S, coortinatPoint T, coortinatPoint P);

int main(){
   int numbersOfPoints;
   coortinatPoint *points;
   printf("Please insert a numbers of point ");
   scanf("%d",&numbersOfPoints);
   points=(coortinatPoint *) malloc(sizeof(coortinatPoint)*numbersOfPoints);
   insertCoortinatesOfPoints(points,numbersOfPoints);

      printConvexHull(points,numbersOfPoints);
   return 0;
}

void insertCoortinatesOfPoints(coortinatPoint *points, int numberOfPoints){
   int i=0;
   for(i=0;i<numberOfPoints;i++){
      printf("Please insert points number %d \n",i+1);
      printf("X=");scanf("%d",&points[i].positionX);
      printf("Y=");scanf("%d",&points[i].positionY);
      points[i].selectedPoint=0;
   }
}

int findMinXPoint(coortinatPoint *points, int numberOfPoints){
   int returnFirstSpoint=0,i;
   for(i=1;i<numberOfPoints;i++){
      if(points[returnFirstSpoint].positionX==points[i].positionX){
         if(points[returnFirstSpoint].positionY>points[i].positionY){
            returnFirstSpoint=i;
         }
      }
      if(points[returnFirstSpoint].positionX>points[i].positionX){
         returnFirstSpoint=i;
      }
   }
   points[returnFirstSpoint].selectedPoint=1;
   return returnFirstSpoint;
}
/*
   If return 1, point P is under line, therefore this point it is located to the right
*/
int checkPointIsRigthFromLine(coortinatPoint S, coortinatPoint T, coortinatPoint P){
   if((P.positionX*(S.positionY-T.positionY)+P.positionY*(T.positionX-S.positionX)+(S.positionX * T.positionY - T.positionX * S.positionY))<0) return 1;
      return 0;
}
void printConvexHull(coortinatPoint *points, int numberOfPoints){
   int positionFirstS=findMinXPoint(points,numberOfPoints),i,firstT;
   coortinatPoint firstS = points[positionFirstS];
   coortinatPoint S = points[positionFirstS];
   printf("x= %d, y=%d \n",firstS.positionX,firstS.positionY);
   /*
   Extract to another function
   */
   for(firstT=0;firstT<numberOfPoints;firstT++){
      if(positionFirstS!=firstT){
         break;
      }
   }
   while (1)
   {
      coortinatPoint T= points[firstT];
      for(i=0;i<numberOfPoints;i++){
         coortinatPoint currentPoint=points[i];
         if(checkPointIsRigthFromLine(S,T,currentPoint)){
            T=currentPoint;      
         }
      }
      if(T.positionX==firstS.positionX && T.positionY==firstS.positionY)break;
    S=T;
    printf("x= %d, y=%d \n",S.positionX,S.positionY);
   }
   
}


Върнете се в началото
 Профил  
 
Покажи мненията от миналия:  Сортирай по  
Напиши нова тема Отговори на тема  [ 17 мнения ]  Отиди на страница Предишна  1, 2

Часовете са според зоната UTC + 2 часа [ DST ]


Кой е на линия

Потребители разглеждащи този форум: 0 регистрирани и 1 госта


Вие не можете да пускате нови теми
Вие не можете да отговаряте на теми
Вие не можете да променяте собственото си мнение
Вие не можете да изтривате собствените си мнения
Вие не можете да прикачвате файл

Иди на:  
cron
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
Превод: Ioan Filipov