8 / 22
Feb 2018

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 :slight_smile:
@narbej ?

Skoro tak ładnie prosisz … :wink:

  1. 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.
  2. Jeżeli używasz C++, to nie używaj C, a w szczególności warto skorzystać z bogactwa biblioteki STL
  3. 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>]
  4. w STL jest sort(), może nie jest szybsza, ale… jest.
  5. 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? :wink:

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ą :wink: A gdzie funkcja ostatnie_namaszczenie i rozgrzeszenie? Mam nadzieję, że się nie gniewasz? :wink: No i czemu ona jest zgrabna? Widziałem naprawdę ładniejsze i zgrabniejsze, a soory, miałem na myśli coś innego …

Dziękuję za wszystkie rady. Doczytam wszystko dokładnie, popoprawiam i oczywiście dodam funkcję ostatnie_namaszczenie :joy: Co do zgrabnej … otrzymała nazwę zanim zacząłem ją pisać, teraz ironicznie przypomina mi ile nauki jeszcze przede mną :slightly_smiling_face:

Mam dwa kolejne pytania :slight_smile:

  1. Czy czas w jakim wynik jest wyświetlany ma znaczenie? Przypuszczam, że mój program liczy szybko, a wolne w tym wypadku jest wyświetlanie.
  2. Jak poradzić sobie z problemem error “Stack overflow” w funkcji Quicksort ???
    (z 8001 punktów daje sobie radę, przy 24000 już nie)

SORRY!!! NIE ZAUWAŻYŁEM! :wink:

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 :wink:

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’

1 month later

Nie wiem czemu kod mi się nie kompiluje :frowning: na komputerze mi wszystko działa a na SPOJu nie. Ma ktoś jakiś pomysł? :slight_smile:

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 :slight_smile: 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?

nawet bardzo nie tak :slight_smile:

to zadanie ma już wątek, poszukaj, przeczytaj, ktoś niestety podał tam (prawie) dobry przepis na rozwiązanie

2 years later

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;
	
}

}

1 month later

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.

Jeżeli Spoj “mówi” przekroczony czas, to może już czas zmienić podejście i wziąść przykład od kolegów powyżej?

1 year later

Cześć ! :slight_smile: 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 :slight_smile:

Link to kodu

Pytanie. W tresci zadania autor opisał kształty pól rolnika jako pewnego typu trójkąty. Pomyśl/zastanów się jakie to ma znaczenie w tym zadaniu.

Hint.
Ołówek [nie zaczarowany - wystarczy zwykły] i kartka papieru. Ewentualnie jakiś program komputerowy do rysowania.

Narysuj dowolny trójkąt, także nie ostrokątny i obrysuj [opisz] go prostokątem, o bokach równoległych odpowiednio do osi x i y.
Powtórz to kilkanaście razy dla różnych położeń trójkąta.

Dzięki :slight_smile: 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ź :slight_smile: 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 :slight_smile: