Cześć wszystkim,
rozwiązanie swojego zadania oparłem na fakcie, iż największe i najmniejsze współrzędne x i y w trójkątach ostrokątnych mają ich wierzchołki. Wyznaczając X max, Y max, X min i Y min jestem w stanie zbudować trójkąt o maksymalnym polu z punktów, do których te współrzędne należą.
Problemem jest natomiast komunikat „przekroczono limit czasu”. Oto kod: https://ideone.com/J5hUum48
Proszę o radę jak kolega powyżej, czy problem leży w pomyśle, w realizacji, czy też dla szczególnych przypadków mój program może się posypać?
Z góry dziękuję za odpowiedź i poświęcony czas
@narbej ?
Skoro tak ładnie prosisz …
- Możesz samodzielnie wygenerować duży test -> 45000/3 pkt np typu
0 0; 1 0; 0 1;
-1 -1 2 0 0 2
-2 -2 3 0 0 3
…
-15000 - 15000 15000 0 0 15000
czy jakoś takie podobne x 50 nawet dokładnie jednakowych i zobaczyć jaK SOBIE [nie]radzi twój program. - Jeżeli używasz C++, to nie używaj C, a w szczególności warto skorzystać z bogactwa biblioteki STL
- Co można lekko usprawnić - bez żadnych gwarancji:
a. dodać ios::sync_with_stdio(0);
b. zamienić wszystkie endl na '\n’
c. zamienić dynamiczne tablice na odpowiednio duże statyczne [lub skorzystać z vector <int>] - w STL jest sort(), może nie jest szybsza, ale… jest.
- Fajnie nazywać pełną nazwą funkcje i zmienne [bardzo wskazane], ale nazwa powinna być natychmiast czytelna także dla czytelnika, daj_glos, a nie lepiej drukuj_wynik?
AD 3.c
Sortujesz tylko fragment statycznej tablicy z aktualnie wpisanymi danymi. Dzięki temu, nie potrzebujesz za każdym razem [max 50 razy] alokować i kasować pamięci…
AD 5
Właściwie, tylko funkcja main() i qucksort() <-- można się domyśleć z samej nazwy do czego są i co prawdopodobnie robią A gdzie funkcja ostatnie_namaszczenie i rozgrzeszenie? Mam nadzieję, że się nie gniewasz?
No i czemu ona jest zgrabna? Widziałem naprawdę ładniejsze i zgrabniejsze, a soory, miałem na myśli coś innego …
SORRY!!! NIE ZAUWAŻYŁEM!
Wyrzuć w swoim pierwotnym kodzie 2x cin.get(); Po co Ci one? Testujesz pod windowsem?
AD 1.
Czas liczy się od uruchomienia do zakończenia działania programu, więc wczytywanie i wypisywanie [ich czas] też się liczy.
AD 2.
Zmienne lokalne [tablice też] umieszczane są na stosie [o ograniczonym rozmiarze]. Użyj statycznej[ych] tablic globalnych, lub dynamicznYCH [deklarowanYCH jednorazowo].
Jednak, weź pod uwagę początek mojego postu i … tyle
EDIT
A jednak to nie to. Po prostu, tak jak na ideone, użyj [do swojego starego kodu] najnowszej wersji kompilatora - a masz ich trochę do wyboru.
PODSUMOWANIE
Nowszy kompilator c++ ver 6.3 jest na tyle dobry, że bez żadnych zmian w twoim “zgrabnym” kodzie wyciśnie i zoptymalizuje go na AC.
Jeżeli chcesz użyć starego [ver 4.32] musisz ytochę “popracować” nad swoim kodem i co naJMNIEJ dodać [wyłączyć] sync_with_stdio oraz prawdopodobnie zamienić endl na ‘\n’
Nie wiem czemu kod mi się nie kompiluje na komputerze mi wszystko działa a na SPOJu nie. Ma ktoś jakiś pomysł?
import java.util.*;
import java.lang.Math.*;
public class Test {
public static void main(String[] args)
{
int d; //number of sets
int numberOfPoints;
int[] x,y;
Scanner scan=new Scanner(System.in);
d= scan.nextInt();
for (int i=0; i<d; i++) //loop for each set
{
ArrayList<Integer> usedIndex=new ArrayList<>();
ArrayList<Integer> pointsInOrder=new ArrayList<>();
scan=new Scanner(System.in);
numberOfPoints=scan.nextInt();
x=new int[numberOfPoints];
y=new int[numberOfPoints];
for (int j=0; j<numberOfPoints;j++) //set x and y of points
{
scan= new Scanner(System.in);
x[j]=scan.nextInt();
scan= new Scanner(System.in);
y[j]=scan.nextInt();
}
for(int j=0; j<x.length/3; j++)
{
int j1=founingMostDistsntPonitFromCenter(x,y,usedIndex);
usedIndex.add(j1);
int j2=foundingMostDistantPointFromPoint(x, y, j1, usedIndex);
usedIndex.add(j2);
int j3=foundingThirdPoint(x,y,j1,j2,usedIndex);
usedIndex.add(j3);
int[] index= {j1,j2,j3};
Arrays.sort(index);
pointsInOrder.add(index[0]);
pointsInOrder.add(index[1]);
pointsInOrder.add(index[2]);
}
for(int j=0; j<numberOfPoints/3; j++)
{
int[] output= {pointsInOrder.get(3*j)+1,pointsInOrder.get(3*j+1)+1,pointsInOrder.get(3*j+2)+1 };
System.out.print(output[0]);
System.out.print(output[1]);
System.out.println(output[2]);
}
System.out.println();
}
}
public static int founingMostDistsntPonitFromCenter(int[] x, int[] y, ArrayList<Integer> used)
{
double d2=-1;
int counter=-1;
for (int j=0; j<x.length;j++) //founds the most distant point
{
double d1= Math.sqrt(Math.pow(x[j],2)+Math.pow(y[j],2));
if (d1>d2 && !used.contains(j))
counter=j;
d2=d1;
}
return counter;
}
public static int foundingMostDistantPointFromPoint(int[] x,int[] y, int index, ArrayList<Integer> used)
{
double d2=-1;
int counter=-1;
for (int j=0; j<x.length;j++) //founds the most distant point
{
double d1= Math.sqrt(Math.pow(x[j]-x[index],2)+Math.pow(y[j]-y[index],2));
if (d1>d2 && !used.contains(j))
{
counter=j;
d2=d1;
}
}
return counter;
}
public static int foundingThirdPoint(int[] x,int[] y, int i1,int i2, ArrayList<Integer> used)
{
double d1,d2=0;
int counter=-1;
for(int j=0; j<x.length;j++)
{
d1=Math.sqrt(Math.pow(x[j]-x[i1],2)+Math.pow(y[j]-y[i1],2))+Math.sqrt(Math.pow(x[j]-x[i2],2)+Math.pow(y[j]-y[i2],2));
if(d1>d2 && !used.contains(j))
{
counter=j;
d2=d1;
}
}
return counter;
}
}
naucz się poprawnie wklejać kod, a jeszcze lepiej przekazuj kod jako link do ideone.com5
gdy klikniesz na napis “błąd kompilacji” dostaniesz listę błędów kompilacji
Dzięki i sory za kod, jestem tu nowy Mam też problem z samym algorytmem. najpierw szukam punktu najbardziej oddalonego od środka układu współrzędnych, potem punktu najbardziej oddalonego od poprzedniego punktu a na koniec punktu najbardziej oddalonego od linii łączącej poprzednie dwa punkty. Czy coś tu jest nie tak?
Hejka, mam problem wywala mi błąd, siedze na tym od dłuższego czasu, mógłby ktoś zerknąć zobaczyć gdzie jest problem? To musi być coś z vectorem, musiałem skopać gdzieś ale nie jestem w stanie na własną reke znalezc gdzie. Prosiłbym bardzo kogoś o pomoc
#include <.iostream>
#include <.vector>
#include <.algorithm>
using namespace std;
struct punkt
{
int x;
int y;
int licznik;
};
bool CompareX(punkt p1,punkt p2)
{
return(p1.x < p2.x);
}
bool CompareY(punkt p1, punkt p2)
{
return(abs(p1.y) < abs(p2.y));
}
bool CompareminX(punkt p1, punkt p2)
{
return(p1.x > p2.x);
}
bool licznik(punkt p1, punkt p2)
{
return(p1.licznik > p2.licznik);
}
int main()
{
int d; cin >> d;
while (d–)
{
int N; cin >> N;
int xTemp, yTemp;
vector Punkt;
int k = N;
int m=N;
for (int i = 0; i < N; i++)
{
cin >> xTemp >> yTemp;
Punkt.push_back({ xTemp,yTemp,i+1 });
}
cout << endl;
vector<punkt> NajwiekszyX = Punkt;
vector<punkt> NajmniejszyX = Punkt;
vector<punkt> NajwiekszyY = Punkt;
sort(NajwiekszyX.begin(), NajwiekszyX.end(), CompareX);
sort(NajmniejszyX.begin(), NajmniejszyX.end(), CompareminX);
sort(NajwiekszyY.begin(), NajwiekszyY.end(), CompareY);
punkt* wskOstPktX;
punkt* wskOstPktXmin;
punkt* wskOstPktY;
wskOstPktX = &NajwiekszyX.back();
wskOstPktXmin = &NajmniejszyX.back();
wskOstPktY = &NajwiekszyY.back();
vector<punkt> trzyPunkty;
while (k > 0)
{
while (wskOstPktY->licznik == wskOstPktX->licznik || wskOstPktY->licznik == wskOstPktXmin->licznik)
{
while (wskOstPktY->licznik == wskOstPktX->licznik)
{
delete wskOstPktY;
NajwiekszyY.pop_back();
wskOstPktY = &NajwiekszyY.back();
}
while (wskOstPktY->licznik == wskOstPktXmin->licznik)
{
delete wskOstPktY;
NajwiekszyY.pop_back();
wskOstPktY = &NajwiekszyY.back();
}
}
trzyPunkty.push_back(NajwiekszyY.back());
trzyPunkty.push_back(NajmniejszyX.back());
trzyPunkty.push_back(NajwiekszyX.back());
delete wskOstPktX;
delete wskOstPktXmin;
if (!NajwiekszyX.empty() || !NajmniejszyX.empty())
{
wskOstPktX = &NajwiekszyX.back();
wskOstPktXmin = &NajmniejszyX.back();
}
NajmniejszyX.pop_back();
NajwiekszyX.pop_back();
NajwiekszyY.pop_back();
sort(trzyPunkty.begin(), trzyPunkty.end(), licznik);
while (!trzyPunkty.empty())
{
cout << trzyPunkty[2].licznik << " ";
cout << trzyPunkty[1].licznik << " ";
cout << trzyPunkty[0].licznik << endl;
trzyPunkty.clear();
}
k = k - 3;
cout << endl;
}
NajwiekszyX.clear();
NajmniejszyX.clear();
NajwiekszyY.clear();
Punkt.clear();
delete wskOstPktX;
delete wskOstPktXmin;
delete wskOstPktY;
}
}
Cześć,
To mój 1 post na forum. Bardzo proszę o pomoc przy tym zadaniu. Wklejam kod z IDEONE14
Ogólnie moje podejście jest nieco inne niż kolegów powyżej - nie sortuje wszystkich punktów tylko szukam ekstrema, nie liczę też pola trójkątów.
Odpowiedź SPOJ: przekroczony czas.
Cześć ! Również mam problem z tym zadaniem, ale w Pythonie 3. Napisałem program który na pewno dobrze je rozwiązuje ( sprawdzałem na większej ilości punktów niż podana na stronie zadania ). Niestety, podobnie jak koledzy wyżej, nie mieszczę się w przewidzianym czasie. Stosuję również podobną metodę - sortuję listę punktów i iteruję po x_min/max, y_min/max i w oparciu o nie konstruuję poszczególne trójkąty. Sprawdzałem z time.time() i wyszło mi że najwięcej czasu poświęcam właśnie na tą pętlę gdzie iteruję po posortowanych listach. Jak waszym zdaniem mógłbym to inaczej rozwiązać ? Z góry dzięki za pomoc
Link to kodu
Dzięki No właśnie nie mogę dostrzec tu innego rozwiązania niż wyznaczenie bądź to 2 punktów - najmniejszego x i największego x - bądź odpowiednio punktów y. Próbowałem 2 sposobów -
-
- użyłem jednej posortowanej listy według osi x i iterowałem po niej od przodu i od tyłu naraz, natomiast brakujący trzeci punkt był pomiędzy nimi - z tym ze musiałem przejść przez wszystkie punkty pomiędzy aby sprawdzić z którym utworzy trójkąt
-
- użyłem 2 list na raz, jednej posotrowanej wg osi x, drugiej y, i najpierw wybierałem 2 skrajne punkty z osi x, oznaczałem jako użyte, następnie 2 skrajne punkty z osi Y, i szukałem w nich właściwego, niestety żadne z rozwiązań nie mieściło sie w czasie
Jest jakiś inny sposób ?
I tak i nie. Ja zaliczyłem to zadanie “twoim drugim sposobem”, ale w C++. W pytonie są tylko 3 AC, ale to bez znaczenia?
Jest takie równanie:
Program = struktury danych + algorytm
Ale tak naprawdę moim zdaniem to:
Mikro Program AC na SPOJU = język programowania + algorytm dostosowany do języka + efektywność zakodowania algorytmu + casami chytre sztuczki programistyczne + struktury danych [czasami chytrze użyute] … itd
Twój pierwszy sposób jest nie tylko bardzo nieefektywnym algorytmem [sposobem] ale dodatkowo nieefektywnie zakodowanym. Jednak nawet różne drobne poprawki i sztuczki i tak dalej będą powodowały TLE. Na przykład do wyszukiwania trzeciego, brakującego punktu użycie liczenia i porównania wielkości pola na danych typu float zamiast int.
Jeżeli IleSposobów = algorytm * sposób zakodowania * struktury danych, to tych sposobów może być naprawdę sporo. Na przykład wyznaczanie otoczki wypukłej [trójkątnej] ale to sosób porównywalny czasowo do twojego pierwszego. Jak napisałem wyżej znam i użyłem sposobu nr 2.
Aby nabyć biegłości w posługiwaniu się narzędziami [język, struktury danych, debuger itd…] należy ćwiczyć, zaczynając od łatwych problemów i warto aby inna osobo sprawdzała twoje rozwiązania i nawzajem - programowanie 2 osobowe, ale nie wspólne rozwiązywanie jednego problemu. Z góry zaznaczam, że ja nie jestem fanem pythona
Dzięki za odpowiedź Generalnie szukałem problemu w algorytmie, pierwszy rzeczywiście był marny. Drugi wydałał się ok, ale nie mieścił sie w czasie. Kilka dni próbowałem znaleźć coś mniej skomplikowanego niż 2, algorytmów convex hull nigdy nie stosowałem, ale też na nie trafiłem szukając rozwiązania z tym że odniosłem wrażenie że wymagałyby zbyt dużej ilości iteracji po punktach i sortowań. Teraz postaram się bardziej ucywilizować kod znaleźć lepszy sposób na strukturę danych. Cóź no komuś udało się to zrobić chyba w 1.6 s. w Py3. Dzięki za sugestie
Suggested Topics
Topic | Category | Replies | Views | Activity |
---|---|---|---|---|
TFRACAL - Kalkulator ułamków | Zbiór zadań | 2 | 170 | Feb 1 |
FR_20_02 - Poszukiwacze skarbów - Błąd w testach? | Zbiór zadań | 1 | 133 | Apr 2 |
SPOJ.com - Problem ZABAWA pl.spoj.com | Zbiór zadań | 6 | 96 | 25d |