Triangoli pienotti

Salve, sto riscontrando difficoltà con questo problema.
Uso l’ algoritmo di Graham che ha O(n log(N)) la complessità del sort in pratica…

Solo che non riesco a superare tutti test case.
é possibile avere qualche output bonus?

Esiste un’ottimizzazione della Graham’s Scan che non usa il compare tra gli angoli (molto lento).

Si chiama Andrew’s monotone chain convex hull algorithm
Esiste un'ottimizzazione della Graham's Scan che non usa il compare tra gli angoli (molto lento).
Si chiama Andrew's monotone chain convex hull algorithm

Lawliet

Ti ringrazio per dritta, comunque perchè l'ordinamento degli angoli sarebbe molto lento?
Se calcoli l'angolo per ogni punto e poi fai il sort è veloce ugualmente, viceversa se calcoli l'angolo nel sort stesso allora si diventa lento.

Comunque mi sembra moooolto molto più semplice quello da te proposto, anche da ricordare.
Domani lo provo ;)

La funzione atan2() è abbastanza lenta con input molto grandi :slight_smile:

Si possono anche ordinare i punti in ordine orario/antiorario non usando gli angoli


UPD: È comunque più semplice usare il Monotone Chain… Comunque ricordati di usare long long e non int, in quanto con i calcoli si possono raggiungere valori molto alti.
La funzione atan2() è abbastanza lenta con input molto grandi :)

Lawliet

Si, più che altro anche quando ci sono angoli vicino ai 90° rallenta molto!
Esiste un'ottimizzazione della Graham's Scan che non usa il compare tra gli angoli (molto lento).
Si chiama Andrew's monotone chain convex hull algorithm

Lawliet

Ho provato l'algoritmo ma mi supera pochi test case.
in output io do
out<<H.size()-1;
dove H è il vettore che contiene i punti dell'inviluppo.
-1 perchè il primo punto è contenuto due volte.

Uso un int per le cordinate e un long long per la funzione cross (ccw) che dovrebbero bastare secondo le assunzioni del problema.

Il fatto è che il problema cosa vuole in output quando ad esempio i punti sono tutti sulla stessa x o sulla stessa y?
cioè quando i punti formano una retta, e quindi non sono presenti triangoli??
Vuole in output semplicemente N?

Perchè il monotone chain in quel caso giustamente da 2 punti, il primo e l'ultimo

Per le coordinate devi usare un float o un double, altrimenti è normale che non funzionerà correttamente perché quando ad esempio c’è una divisione tra un double e un int, verrà fatta la divisione intera anche se il risultato deve andare in un float, e questo ovviamente ti taglierà la parte decimale dandoti dei risultati errati.

Inoltre se tutti i punti sono su una retta l’algoritmo dovrebbe tranquillamente ritornare N, se non sbaglio.
Per le coordinate devi usare un float o un double, altrimenti è normale che non funzionerà correttamente perché quando ad esempio c'è una divisione tra un double e un int, verrà fatta la divisione intera anche se il risultato deve andare in un float, e questo ovviamente ti taglierà la parte decimale dandoti dei risultati errati.
Inoltre se tutti i punti sono su una retta l'algoritmo dovrebbe tranquillamente ritornare N, se non sbaglio.

Lawliet

dove vengono fatte divisioni nell'algoritmo??
Io non ne vedo

Quello della divisione era un esempio. Hai già provato ad usare un float o un double?


EDIT: ho provato ad usare quest’algoritmo con coordinate intere e mi da 0/100. Evidentemente il problema è quello
Quello della divisione era un esempio. Hai già provato ad usare un float o un double?

EDIT: ho provato ad usare quest'algoritmo con coordinate intere e mi da 0/100. Evidentemente il problema è quello

Lawliet

Risolto con long long, ho preso 100/100

Hai fatto il casting in (long long) nella funzione ccw? Perché anche se ritorna long long, ma lavora con int, va in overflow lo stesso (dato che il massimo per le assunzioni è 2^63)

Hai fatto il casting in (long long) nella funzione ccw? Perché anche se ritorna long long, ma lavora con int, va in overflow lo stesso (dato che il massimo per le assunzioni è 2^63)

mark03

usando il casting ed usando un long long per le cordinate da anche a me 100/100

Comunque resta il fatto che se l'input è ad esempio:

4
1 1
2 1
3 1
4 1

L'output dovrebbe essere N, mentre l'algoritmo da come out 2, i punti (1,1) e (4,1).
Quindi in realtà se il problema avesse dei testcase come sopra bisognerebbe fare prima un piccolo check sulle cordinate per vedere se sono tutte sulla stessa retta, e poi in caso contrario fare il monotone chain

L’output è giusto 2, in quanto non devono essere per forza interni al triangolo, ma possono anche appartenere ad un lato…

L'output è giusto 2, in quanto non devono essere per forza interni al triangolo, ma possono anche appartenere ad un lato...

mark03

Certo, ma in quel caso non c'è nessun triangolo al cui lato possono appartenere

Se consideri il triangolo che degenera in un segmento si che c’è

Se consideri il triangolo che degenera in un segmento si che c'è

mark03

mhh..
Sì, ci può stare, ma dato che non specifica è un po a libera interpretazione

Ho provato a risolvere questo problema implementando un mio algoritmo…

Il codice è qui:

#include <stdio.h>
#include <algorithm>
#include <deque>

using namespace std;
 
struct Point {
	long double x,y;
//	char c;
};

int func(deque<Point> p){
	
	int out = 0;
	
	// cerco il punto che sta più in basso e a parità di y quello più a destra
	int minY = 0;
	for(int i=1; i<p.size(); i++)
		if(p[i].y < p[minY].y || (p[i].y == p[minY].y && p[i].x > p[minY].x))
			minY = i;
//	printf("%c\n\n\n", p[minY].c);
	
	int ok,ok2;
	double angle;
	
	// salvo le coordinate del punto
	long double x = p[minY].x, y = p[minY].y;
	
	// salvo il primo punto
	struct Point primo = p[minY];
	// elimino il primo punto
	p.erase(p.begin()+minY);
	
	// primo ciclo
	do{
		ok = -1;
		ok2 = -1;
		
		for(int i=0; i<p.size(); i++)
			if(x != p[i].x){
				
				double a = (double)(p[i].y-y)/(p[i].x-x);
				
				if(a>0 && x<p[i].x){
					if(ok == -1){
						ok = i;
						angle = a;
					}
					else{
						if(a < angle){
							ok = i;
							angle = a;
						}
						else
							if(a == angle)
								if(p[i].x > p[ok].x)
									ok = i;
					}
				}
			}
			else{
				if(ok == -1){
					if(ok2 == -1)
						ok2 = i;
					else
						if(p[ok2].y > p[i].y)
							ok2 = i;
				}
			}
		
		if(ok != -1){
			out++;
			x = p[ok].x;
			y = p[ok].y;
//			printf("%c\n", p[ok].c);
			p.erase(p.begin()+ok);
		}
		else
			if(ok2 != -1){
				out++;
				x = p[ok2].x;
				y = p[ok2].y;
//				printf("%c\n", p[ok2].c);
				p.erase(p.begin()+ok2);
			}
		
	}while(ok != -1);
	
	// secondo ciclo
	do{	
		ok = -1;
		ok2 = -1;
		
		for(int i=0; i<p.size(); i++)
			if(x != p[i].x)
				if(y != p[i].y){
					
					double a = (double)(p[i].y-y)/(p[i].x-x);
					
					if(a<0 && x>p[i].x){
						if(ok == -1){
							ok = i;
							angle = a;
						}
						else{
							if(a < angle){
								ok = i;
								angle = a;
							}
							else
								if(a == angle)
									if(p[i].x < p[ok].x)
										ok = i;
						}
					}
				}
				else{
					if(ok == -1){
						if(ok2 == -1)
							ok2 = i;
						else
							if(p[ok2].x > p[i].x)
								ok2 = i;
					}
				}
		
		
		if(ok != -1){
			out++;
			x = p[ok].x;
			y = p[ok].y;
//			printf("%c\n", p[ok].c);
			p.erase(p.begin()+ok);
		}
		else
			if(ok2 != -1){
				out++;
				x = p[ok2].x;
				y = p[ok2].y;
//				printf("%c\n", p[ok2].c);
				p.erase(p.begin()+ok2);
			}
	
	}while(ok != -1);
	
	// rimetto il primo punto nella lista per poter chiudere il cerchio
	p.push_back(primo);
	
	// terzo ciclo
	do{		
		ok = -1;
		ok2 = -1;
		
		for(int i=0; i<p.size(); i++)
			if(x != p[i].x){
				
				double a = (double)(p[i].y-y)/(p[i].x-x);
				
				if(a>0 && x>p[i].x){
					if(ok == -1){
						ok = i;
						angle = a;
					}
					else{
						if(a < angle){
							ok = i;
							angle = a;
						}
						else
							if(a == angle)
								if(p[i].x < p[ok].x)
									ok = i;
					}
				}
			}
			else{
				if(ok == -1){
					if(ok2 == -1)
						ok2 = i;
					else
						if(p[ok2].y > p[i].y)
							ok2 = i;
				}
			}
		
		if(ok != -1){
			out++;
			x = p[ok].x;
			y = p[ok].y;
//			printf("%c\n", p[ok].c);
			p.erase(p.begin()+ok);
		}
		else
			if(ok2 != -1){
				out++;
				x = p[ok2].x;
				y = p[ok2].y;
//				printf("%c\n", p[ok2].c);
				p.erase(p.begin()+ok2);
			}
	
	}while(ok != -1);
	
	// quarto e ultimo ciclo
	do{
		ok = -1;
		ok2 = -1;
		
		for(int i=0; i<p.size(); i++)
			if(x != p[i].x)
				if(y != p[i].y){
					
					double a = (double)(p[i].y-y)/(p[i].x-x);
					
					if(a<0 && x<p[i].x){
						if(ok == -1){
							ok = i;
							angle = a;
						}
						else{
							if(a < angle){
								ok = i;
								angle = a;
							}
							else
								if(a == angle)
									if(p[i].x > p[ok].x)
										ok = i;
						}
					}
				}
				else{
					if(ok == -1){
						if(ok2 == -1)
							ok2 = i;
						else
							if(p[ok2].y > p[i].y)
								ok2 = i;
					}
				}
		
	if(ok != -1){
		out++;
		x = p[ok].x;
		y = p[ok].y;
//		printf("%c\n", p[ok].c);
		p.erase(p.begin()+ok);
	}
	else
		if(ok2 != -1){
			out++;
			x = p[ok2].x;
			y = p[ok2].y;
//			printf("%c\n", p[ok2].c);
			p.erase(p.begin()+ok2);
		}
	
	
	}while(ok != -1);
	
	return out;
}

main(){	
    FILE *pF = fopen("input.txt", "r");
    int n;
    fscanf(pF, "%d", &n);
    int i;
    deque<Point> p;
    struct Point x;
    int a,b;
    for(i=0; i<n; i++){
    	fscanf(pF, "\n%d %d", &a, &b);
    	x.x = (long double)a;
    	x.y = (long double)b;
//    	x.c = 'a'+i;
    	p.push_back(x);
    }
    if(p.size()<4)
    	return 123;
	int ris = func(p);
//	printf("%d", ris);
    FILE *pF2 = fopen("output.txt", "w");
    fprintf(pF2, "%d", ris);
	fclose(pF2);	
}

( http://pastebin.com/syTcHhX8 )

La mia idea è che posso disegnare una sorta di poligono in cui tutti i punti che non sono vertici stanno dentro il poligono oppure sui suoi lati. Così facendo il problema si risolve semplicemente contando i vertici.

L’algoritmo è:

  • cerco il punto che sta più in basso e a parità di y quello più a destra
  • calcolo il coefficiente angolare della retta che passa fra il punto preso e tutti gli altri e prendo il punto il cui coeff. ang. è minimo fra quelli positivi e vado avanti finchè posso andare verso destra e verso l’alto o solo in verticale
  • ripeto l’ultimo passo altre tre volte per completare l’ipotetico cerchio in cui sono compresi tutti i punti
  • il risultato del problema è il numero dei punti passati (il primo e l’ultimo sono uguali quindi li prendo una sola volta)

Il codice funziona tranne che per 2 test-case in cui il risultato è sbagliato (per altri 4 test-case va in time-out, ma è abbastanza ovvio perché il codice è poco ottimizzato). Dimentico qualche caso particolare che il mio algoritmo non è in grado di risolvere?