droogy utworzono 13 stycznia 2009 utworzono 13 stycznia 2009 Proszę was o pomoc w napisaniu programu... jest to dosc ciekawy algorytm. Mam nie wiele czasu na napisanie tego i w miedzy czasie mase innych zaliczen:/ jezeli ktos ma taki program lub wie jak go napisac to prosze o udostepnienie swojej wiedzy. tresc: Napisac program w C, ktory wykona n losowań czterech punktow na płaszczyźnie 2D z zakresu [0,10][0,10], nastepnie sprawdzi czy da sie z wylosowanych punktow zbudowac figure o obrysie wklęslym. Jeżeli da sie to obliczyć jej obwod. Znaleźć figury o najmniejszym i najwiekszym obwodzie oraz posortowac figury w zależnosci od wielkosci obwodu. Wyniki zapisac do pliku. Z gory dziekuje.
rafalluz komentarz 13 stycznia 2009 komentarz 13 stycznia 2009 Dwa pytania: 1. To jest tak, że n razy losujemy 4 punkty i sprawdzamy dla każdej czwórki z osobna? Czy może sprawdzamy dla tych 4*n punktów? (Bardziej prawdopodobnie brzmi to pierwsze, ale nie wiem) 2.Jest założenie, że figura ma być wielokątem? Czy punkty moga łaczyć jakieś fikuśne krzywe?
droogy komentarz 14 stycznia 2009 Autor komentarz 14 stycznia 2009 Figura ma być wielokątem złożonym z czterech punktów... czyli losujemy n czworokątów i kazdy z osobna sprawdzamy...
rafalluz komentarz 14 stycznia 2009 komentarz 14 stycznia 2009 Skoro tak, to masz 4 punkty (p1, p2, p3 i p4) i 24 ich permutacje (czyli kolejności połączenia wierzchołków). Ale: -Musisz to podzielić przez 4, bo niektóre z tych permutacji dadzą to samo np. po kolei (p1, p2, p3, p4) da to samo, co (p2, p3, p4, p1), (p3, p4, p1, p2) i (p4, p1, p2, p3) -Musisz jeszcze podzielić przez 2, bo możesz łączyć w 2 strony, np (p1, p2, p3, p4) i (p4, p3, p2, p1) da to samo. I analogicznie dla reszty wymienionych permutacji Wzór wyjdzie (n-1)!/2 czyli 3 dla n=4. Tyle to możesz sprawdzić z osobna. Interesują Cię permutacje: (p1, p2, p3, p4) (p1, p2, p4, p3) (p1, p3, p2, p4) lub inne analogiczne do nich. Jak nie widzisz, możesz sobie rozrysować na kartce. Czyli wystarczy, że dla każdej z tych trzech sprawdzisz, czy jest ten obrys (tego nie ustaliłem, co to jest) i policzysz obwód (oczywiście sumując długości odcinków). Sort i zapis do pliku to raczej jasne.
droogy komentarz 14 stycznia 2009 Autor komentarz 14 stycznia 2009 Wlasnie najwiekszy problem jest ze sprawdzeniem obrysu:/ ale dzieki za cenne wskazowki:)
rafalluz komentarz 14 stycznia 2009 komentarz 14 stycznia 2009 Masz jakąś definicję/materiały odnośnie tego? Nie spotkałem się z tym pojęciem przez swoją edukację, google też konkretów za bardzo nie zwraca.
falcon1984 komentarz 14 stycznia 2009 komentarz 14 stycznia 2009 Czworokąt wklęsły to taki, w który można poprowadzić odcinek łączący dwa punkty należącego do wnętrza tego czworokąta w taki sposób że część tego odcinka znajdzie się poza czworokątem: A jak sprawdzić czy dane 4 punkty utworzą wklęsły czworokąt ? Wydaje mi się że trzeba sprawdzić wszystkie możliwe zbiory 3 punktów tego czworokąta, zbudować na ich podstawie trójkąt i sprawdzić czy 4 punkt leży wewnątrz tego trójkąta. Jeśli w co najmniej 1 przypadku tak to figura jest wklęsła Obliczenie obwodu, posortowanie i zapis do pliku to już nie problem
rafalluz komentarz 14 stycznia 2009 komentarz 14 stycznia 2009 Po prostu zbadać, czy figura jest wklęsła? Heh, tak myślałem niby, ale ten 'obrys' i tak mnie martwi Ta metoda sprawdzania wklęsłości nie przejdzie. Sprawdź ten przypadek: Tutaj zawsze czwarty punkt będzie poza trójkątem, ale figura jest wklęsła. Jak trzeba zbadać wklęsłość, to proponuję sprawdzić, czy obie przekątne leżą wewnątrz wielokąta. Jak nie, to jest wklęsła. Ma moje to trzeba sprawdzić, czy pozostałe dwa punkty (ni połączone spawdzaną przekątną) leżą po tej samej stronie danej przekątnej. Jak tak, to przekątna leży na zewnątrz. Aaaaa, i możesz jeszcze wcześniej sprawdzić, czy żadne 3 (lub 4) punkty nie są współliniowe, ale to chyba mało prawdopodobny przypadek.
droogy komentarz 25 stycznia 2009 Autor komentarz 25 stycznia 2009 napisalem znaczna czesc tego programu... jest tu jakis błąd merytoryczny i nie moge go znaleźć... pomóżcie prosze... #include <stdio.h>#include <stdlib.h>#include <time.h>#include <math.h>int rand();int n;void main(){ printf("Podaj liczbe figur do wylosowania\n"); scanf("%d",&n); srand((unsigned)time(NULL)); int N=n*4; int M=2; double x0=10.; double y0=10.; int a=0; double**tab=(double**)malloc(N*M*sizeof(double)); for(int l=0;l<2;l++) { tab[l]=(double*)malloc(N*sizeof(double)); } for(int j=0;j<N;j++) { for(int i=0;i<2;i++) { if(i==0) tab[i][j]=x0*rand()/(double) RAND_MAX; else tab[i][j]=y0*rand()/(double) RAND_MAX; if(((a)%8)==0) { printf("\n\n"); printf("Figura nr. %d\n\n",((a/8)+1)); } printf("%lf\n",tab[i][j]); a++; } } { int C=4; double**pole=(double**)malloc(n*C*sizeof(double)); for(int k=0;k<4;k++) { tab[k]=(double*)malloc(n*sizeof(double)); } double a,b,c,d,e,f,o1,o2,o3,o4; for(int h=1;h<n;h++) { a=sqrt(pow(tab[((h-1)*4)+2][1]-tab[((h-1)*4)+1][1],2)+pow(tab[((h-1)*4)+2][2]-tab[((h-1)*4)+1][2],2)); b=sqrt(pow(tab[((h-1)*4)+3][1]-tab[((h-1)*4)+1][1],2)+pow(tab[((h-1)*4)+3][2]-tab[((h-1)*4)+1][2],2)); c=sqrt(pow(tab[((h-1)*4)+4][1]-tab[((h-1)*4)+1][1],2)+pow(tab[((h-1)*4)+4][2]-tab[((h-1)*4)+1][2],2)); d=sqrt(pow(tab[((h-1)*4)+3][1]-tab[((h-1)*4)+2][1],2)+pow(tab[((h-1)*4)+3][2]-tab[((h-1)*4)+2][2],2)); e=sqrt(pow(tab[((h-1)*4)+4][1]-tab[((h-1)*4)+2][1],2)+pow(tab[((h-1)*4)+4][2]-tab[((h-1)*4)+2][2],2)); f=sqrt(pow(tab[((h-1)*4)+4][1]-tab[((h-1)*4)+3][1],2)+pow(tab[((h-1)*4)+4][2]-tab[((h-1)*4)+3][2],2)); o1=(a+c+e)/2; o2=(c+b+f)/2; o3=(e+d+f)/2; o4=(a+b+d)/2; pole[h][1]=(sqrt(o1*(o1-a)*(o1-c)*(o1-e))); pole[h][2]=(sqrt(o2*(o2-c)*(o2-b)*(o2-f))); pole[h][3]=(sqrt(o3*(o3-e)*(o3-d)*(o3-f))); pole[h][4]=(sqrt(o3*(o4-a)*(o4-b)*(o4-d))); if(pole[h][1]+pole[h][2]+pole[h][3]==pole[h][4]||pole[h][1]+pole[h][2]+pole[h][4]==pole[h][3]||pole[h][2]+pole[h][3]+pole[h][4]==pole[h][1]||pole[h][3]+pole[h][4]+pole[h][1]==pole[h][2]) printf("Figura nr.%d jest wklęsła\n",h); } }}
Kajot komentarz 29 stycznia 2009 komentarz 29 stycznia 2009 algorytm na tzw otoczkę wypukłą, jesli wszystkie punkty zbioru tworza ta otoczke - jest to wielokat wypukly, jesli nie - nie ewentualny punkt NIEnalezacy do otoczki bedzie tym "wklęśnietym" tak mi sie wydaje pokrotce, nie zastanawialem sie nad tym dluzej http://www.algorytm.org/index.php?option=c...0&Itemid=28
Wciąż szukasz rozwiązania problemu? Napisz teraz na forum!
Możesz zadać pytanie bez konieczności rejestracji - wystarczy, że wypełnisz formularz.