Witam,
zająłem się problemem nr 26 http://www.spoj.com/problems/BSHEEP/ jednak dostaję tle, zastosowałem graham scan i sort z biblioteki algorithm, jako, że moje poprzednie podejście z algorytmem jarvisa miało zbyt dużą złożoność obliczeniową (sięgało O(n^2))... Graham działa w nlogn, podobnie jak sort. Vector z punktami wymaga modyfikacji żeby usunąć wierzchołki powtarzające się oraz wierzchołki o tym samym kącie z osią x, poza tym o najdłuższej odległości. Te operacje podobnie jak inicjalizacja na moje oko to złożoność liniowa, nie wiem czy da się to jakoś zoptymalizować... Będę wdzięczny jeśli ktoś rzuci okiem : )
#include <cstdio>
#include <math.h>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;
unsigned n;
float minx, miny;
float ax = 1.0;
float ay = 0.0;
float la = 1.0;
struct point
{
unsigned id;
double alfa;
int x;
int y;
};
float ccw(point p1, point p2, point p3)
{
return ( (p2.x - p1.x)*(p3.y - p1.y) - (p2.y - p1.y)*(p3.x - p1.x) );
}
inline float angle(float x, float y)
{
float len = sqrt( (x - minx)*(x - minx) + (y - miny)*(y - miny) );
float kx = x - minx;
float ky = y - miny;
float c = ((ax)*(kx) + (ay)*(ky))/(la*len);
float alfa = acos(c)*180/3.141592;
if(alfa != alfa) alfa = -1.0;
alfa = ceilf(alfa * 100) / 100;
return alfa;
}
struct pkt_less {
bool operator ()(point const& a, point const& b) const {
if (a.alfa < b.alfa) return true;
if (a.alfa > b.alfa) return false;
return false;
}
};
struct soz {
bool operator ()(point const& a, point const& b) const {
float s = (sqrt( ((a).x - minx)*((a).x - minx) + ((a).y - miny)*((a).y - miny) ) -
sqrt( (((b)).x - minx)*(((b)).x - minx) + (((b)).y - miny)*(((b)).y - miny) ) );
if ( s < 0 ) {return true; }
if ( s == 0) { if(a.id < b.id) {return false;} else return true;}
else return false;
}
};
int main ()
{
int x, y;
unsigned s, n;
vector<point> points;
vector<point> hull;
vector<point>::iterator it,j,p;
scanf("%d",&s);
while(s)
{
unsigned c = 1;
printf("\n");
scanf("%d",&n);
for(unsigned i=0;i<n;++i)
points.push_back(point());
for(p=points.begin();p!=points.end();++p)
{
scanf("%d %d",&x,&y);
(*p).x = x; (*p).y = y; (*p).id = c;
if(y<miny) { miny=y; minx = x;}
else if(y==miny) { if(x<minx) {minx = x;} }
++c;
}
for(p=points.begin();p!=points.end();++p)
(*p).alfa = angle((*p).x, (*p).y);
sort(points.begin(), points.end(), pkt_less());
for(p = points.begin(); p!=(points.end()) ;++p)
{
unsigned r=1;
vector<point> swapper;
swapper.push_back(*p);
while( ((*p).alfa) == ((*(p+1)).alfa) && p!=points.end()-1 )
{
swapper.push_back(*(p+1));
++p;
++r;
}
if(swapper.size()>1)
{
sort(swapper.begin(), swapper.end(), soz() );
swapper.erase(swapper.begin(),swapper.end()-1);
points.erase(p-r+1,p+1);
points.insert(p-r+1, swapper.begin(), swapper.end());
p = p-r;
}
swapper.clear();
}
if(n>1)
{
hull.push_back(*(points.begin()));
hull.push_back(*(points.begin()+1));
for(p=points.begin()+2;p!=points.end();++p)
{it = j = hull.end()-1; --it;
if(ccw((*it),(*j),(*p)) >= 0){ hull.push_back(*p);}
else
{it = j = hull.end()-1; --it;
while( (ccw((*it),(*j),(*p)) <= 0 )) { hull.pop_back(); it = j = hull.end()-1; --it;}
hull.push_back(*p);
}
}
}else
{
hull.push_back(*(points.begin()));
}
hull.push_back(*(points.begin()));
float distance = 0.0;
for(vector<point>::iterator it=hull.begin(); it!=hull.end();++it)
{
if(it!=hull.end()-1) distance += ( sqrt( ((*(it+1)).x - (*it).x) * ((*(it+1)).x - (*it).x) + ((*(it+1)).y - (*it).y) * ((*(it+1)).y - (*it).y) ) );
}
printf("%.2f\n", distance);
for(vector<point>::iterator it=hull.begin(); it!=hull.end()-1;++it)
{
if(it!=hull.begin()) printf(" ");
printf("%d",(*it).id);
}
printf("\n");
points.clear();
hull.clear();
--s;
}
return 0;
}
Znowu na serwisie uva judge, z problemem do rozwiązania którego zastosowałem te same algorytmy dostaje werdykt 'wrong answer' mimo, że sprawdzałem wejście i wyjście dla setek automatycznie generowanych wierzchołków i wszystko śmigało... Nie przeszło przez testy, jednak nie dostałem tle..
Jeśli ktoś chce zerknąć http://online-judge.uva.es/board/viewtopic.php?f=2&t=75930&p=213871#p213871
