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).
Esiste un'ottimizzazione della Graham's Scan che non usa il compare tra gli angoli (molto lento).Ti ringrazio per dritta, comunque perchè l'ordinamento degli angoli sarebbe molto lento?Lawliet
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 
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 :)Si, più che altro anche quando ci sono angoli vicino ai 90° rallenta molto!Lawliet
Esiste un'ottimizzazione della Graham's Scan che non usa il compare tra gli angoli (molto lento).Ho provato l'algoritmo ma mi supera pochi test case.Lawliet
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.dove vengono fatte divisioni nell'algoritmo??Inoltre se tutti i punti sono su una retta l'algoritmo dovrebbe tranquillamente ritornare N, se non sbaglio.Lawliet
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?Risolto con long long, ho preso 100/100EDIT: ho provato ad usare quest'algoritmo con coordinate intere e mi da 0/100. Evidentemente il problema è quelloLawliet
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)usando il casting ed usando un long long per le cordinate da anche a me 100/100mark03
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...Certo, ma in quel caso non c'è nessun triangolo al cui lato possono apparteneremark03
Se consideri il triangolo che degenera in un segmento si che c’è
Se consideri il triangolo che degenera in un segmento si che c'èmhh..mark03
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?