pomysł w połowie dobry, w połowie zły
realizacja (prawie) w całości zła
ponieważ moje uwagi do programu zbyt ułatwiły by innym zadanie (choć mam wrażenie że nikt nie szuka i nie czyta już założonych wątków) to prześlę je na priv (gdy będę miał wolne 15 minut )

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 …

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?

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 …

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

Mam dwa kolejne pytania

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!

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?

nawet bardzo nie tak

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

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.

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

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

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.

A mógłbyś spróbować naprowadzić mnie nieco bardziej ?

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

1. • 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
2. • 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 ?