Pagini recente » Cod sursa (job #3336046) | Cod sursa (job #16384) | Cod sursa (job #1045192) | Cod sursa (job #93553) | Cod sursa (job #3355100)
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct POINT{
double x,y;
};
POINT v[120005];
POINT LL;
const double eps=1.e-12;
bool compar(POINT P1,POINT P2)
{
if(P2.y-P1.y <= -eps)
return 1;
else
if(fabs(P2.y-P1.y)<eps && P2.x-P1.x<=-eps)
return 1;
else
return 0;
}
double cp(POINT P1,POINT P2,POINT P3)
{
return (P2.x-P1.x)*(P3.y-P2.y)-(P2.y-P1.y)*(P3.x-P2.x);
}
int ccw(POINT P1,POINT P2,POINT P3)
{
double product;
product=cp(P1,P2,P3);
if(fabs(product)<eps)
return 0;
if(product>=eps)
return 1;
return -1;
}
bool cmp(POINT A,POINT B)
{
if(ccw(LL,A,B)==-1)
return 0;
return 1;
}
int main()
{
int n,i,top;
fin>>n;
fin>>v[1].x>>v[1].y;
for(i=2;i<=n;i++)
{
fin>>v[i].x>>v[i].y;
if(compar(v[1],v[i]))
swap(v[1],v[i]);
}
LL=v[1];
sort(v+2,v+n+1,cmp);
v[n+1]=LL;
//Infasuratoarea convexa/Convex Hull
int h[120005];
h[1]=1;
h[2]=2;
top=2;
i=3;
while(i<=n+1)
{
if(ccw(v[h[top-1]],v[h[top]],v[i])>0)
{
h[++top]=i;
i++;
}
else
top--;
}
top--;
fout<<top<<"\n";
for(i=1;i<=top;i++)
{
fout<<fixed<<showpoint<<setprecision(6)<<v[h[i]].x<<" "<<v[h[i]].y<<"\n";
}
// adaug pct 1, adaug pct 2, de la al treilea verific cum
// este orientat fata de p1 si p2
// e in sens trig il adaug, la fel si p4
// de la p5 face misc in sens orar
// deci il scot pe p4 din stiva si il adaug pe p5
// si analizez p2p3p5 si daca e bun il adaug
// p6 merge il adaug dar la p7 nu merge
// scot p6, verific p3p5p7
return 0;
}