# Triangoli pienotti

**URL:** <https://forum.olinfo.it/t/triangoli-pienotti/3813>\
**Category:** Aiuto\
**Created:** [12 Luglio 2014, 6:13pm UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813 "2014-07-12T18:13:02Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [12 Luglio 2014, 6:13pm UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/1 "2014-07-12T18:13:02Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [11 Agosto 2014, 8:47pm UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/2 "2014-08-11T20:47:45Z")

</div>

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

Si chiama&nbsp;**[Andrew’s monotone chain convex hull algorithm](http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#C.2B.2B)**

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [12 Agosto 2014, 5:26pm UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/3 "2014-08-12T17:26:53Z")

</div>

> Esiste un'ottimizzazione della Graham's Scan che non usa il compare tra gli angoli (molto lento).
> Si chiama&nbsp;**[Andrew's monotone chain convex hull algorithm](http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#C.2B.2B)**
> 
> 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 ;)

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [12 Agosto 2014, 5:31pm UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/4 "2014-08-12T17:31:41Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [12 Agosto 2014, 6:19pm UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/5 "2014-08-12T18:19:54Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![EmanueleRossi](https://forum.olinfo.it/user_avatar/forum.olinfo.it/emanuelerossi/32/42_2.png) [@EmanueleRossi](https://forum.olinfo.it/u/EmanueleRossi)\
**Post date:** [15 Agosto 2014, 8:47pm UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/6 "2014-08-15T20:47:31Z")

</div>

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

Si, più che altro anche quando ci sono angoli vicino ai 90° rallenta molto!

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [16 Agosto 2014, 10:14am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/7 "2014-08-16T10:14:06Z")

</div>

> Esiste un'ottimizzazione della Graham's Scan che non usa il compare tra gli angoli (molto lento).
> Si chiama&nbsp;**[Andrew's monotone chain convex hull algorithm](http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain#C.2B.2B)**
> 
> 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

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [16 Agosto 2014, 10:38am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/8 "2014-08-16T10:38:24Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [16 Agosto 2014, 10:41am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/9 "2014-08-16T10:41:17Z")

</div>

> 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

---

<div class="post-metadata">

**Author:** ![Lawliet](https://forum.olinfo.it/user_avatar/forum.olinfo.it/lawliet/32/28_2.png) [@Lawliet](https://forum.olinfo.it/u/Lawliet)\
**Post date:** [16 Agosto 2014, 11:00am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/10 "2014-08-16T11:00:43Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [16 Agosto 2014, 11:31am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/11 "2014-08-16T11:31:33Z")

</div>

> 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

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [16 Agosto 2014, 11:35am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/12 "2014-08-16T11:35:08Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [17 Agosto 2014, 7:57am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/13 "2014-08-17T07:57:20Z")

</div>

> 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

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [17 Agosto 2014, 8:01am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/14 "2014-08-17T08:01:02Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![Degiac](https://forum.olinfo.it/user_avatar/forum.olinfo.it/degiac/32/9_2.png) [@Degiac](https://forum.olinfo.it/u/Degiac)\
**Post date:** [17 Agosto 2014, 8:06am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/15 "2014-08-17T08:06:35Z")

</div>

> 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

---

<div class="post-metadata">

**Author:** ![mark03](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/439d5e/32.png) [@mark03](https://forum.olinfo.it/u/mark03)\
**Post date:** [17 Agosto 2014, 8:34am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/16 "2014-08-17T08:34:30Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![simone.pri](https://forum.olinfo.it/user_avatar/forum.olinfo.it/simone.pri/32/18_2.png) [@simone.pri](https://forum.olinfo.it/u/simone.pri)\
**Post date:** [17 Agosto 2014, 8:55am UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/17 "2014-08-17T08:55:56Z")

</div>

> 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

---

<div class="post-metadata">

**Author:** ![marcoBeretta](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/m/ed655f/32.png) [@marcoBeretta](https://forum.olinfo.it/u/marcoBeretta)\
**Post date:** [21 Agosto 2014, 7:33pm UTC](https://forum.olinfo.it/t/triangoli-pienotti/3813/18 "2014-08-21T19:33:56Z")

</div>

Ho provato a risolvere questo problema implementando un mio algoritmo…

Il codice è qui:

```auto
#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](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?