Pagini recente » Cod sursa (job #2734717) | Cod sursa (job #1409242) | Cod sursa (job #1548027) | Cod sursa (job #2174675) | Cod sursa (job #870539)
Cod sursa(job #870539)
#include <fstream>
#include <cmath>
#include <algorithm>
#define nmax 12001
#define eps 1e-12
using namespace std;
struct punct{
double x,y;
};
punct P[nmax],HULL[nmax],LH[nmax],UH[nmax];
int N,NH,NLH,NUH;
double delta(punct &p1,punct &p2,punct &p3)
{
return(
p1.x*p2.y+p2.x*p3.y+p3.x*p1.y-p3.x*p2.y-p1.x*p3.y-p2.x*p1.y);
}
inline bool cmp(punct p1,punct p2)
{
if(fabs(p1.x-p2.x)<=eps)
if(p1.y<p2.y)
return true;
else
return false;
else
if(p1.x<p2.x)
return true;
else
return false;
}
void MonotoneChain()
{
sort(P+1,P+N+1,cmp);
int i;
for(i=1;i<=N;i++)
{
while(NLH>=2 && delta(LH[NLH-1],LH[NLH],P[i])<=0.f)
--NLH;
LH[++NLH]=P[i];
}
for(i=N;i>=1;i--)
{
while(NUH>=2 && delta(UH[NUH-1],UH[NUH],P[i])<=0.f)
--NUH;
UH[++NUH]=P[i];
}
--NLH;
--NUH;
for(i=1;i<=NLH;i++)
HULL[i]=LH[i];
for(i=1;i<=NUH;i++)
HULL[i+NLH]=UH[i];
NH=NLH+NUH;
}
void citeste()
{
ifstream f("infasuratoare.in");
int i;
f>>N;
for(i=1;i<=N;i++)
f>>P[i].x>>P[i].y;
f.close();
}
void scrie()
{
ofstream g("infasuratoare.out");
int i;
g<<NH<<'\n';
for(i=1;i<=NH;i++)
g<<HULL[i].x<<' '<<HULL[i].y<<'\n';
g.close();
}
int main()
{
//cout << "Hello world!" << endl;
citeste();
MonotoneChain();
scrie();
return 0;
}