Pagini recente » Cod sursa (job #2548094) | Cod sursa (job #2162394) | Cod sursa (job #682204) | Cod sursa (job #1658231) | Cod sursa (job #913936)
Cod sursa(job #913936)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define NMAX 120005
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
long N,i1,st[NMAX],k;
struct pct{double x,y;}P[NMAX];
double x1,y1;
bool cmp(pct p1,pct p2)
{
return (p1.y-y1)*(p2.x-x1) < (p2.y-y1)*(p1.x-x1) ;
}
bool pl(long i ,long j , long k1)
{
return ( (P[i].x*P[j].y)+(P[j].x*P[k1].y)+(P[i].y*P[k1].x)-(P[j].y*P[k1].x)-(P[k1].y*P[i].x)-(P[i].y*P[j].x) ) > 0 ;
}
void infas()
{
st[1]=1;
k=1;
for (int i=2;i<=N;i++)
{
while(k>1&&pl(st[k],st[k-1],i)) k--;
st[++k]=i;
}
}
int main()
{
f>>N;
x1=1000000001;
for (long i=1;i<=N;i++)
{
f>>P[i].x>>P[i].y;
if (P[i].x==x1&&P[i].y<y1) {x1=P[i].x; y1=P[i].y; i1=i;}
if (P[i].x<x1) {x1=P[i].x; y1=P[i].y; i1=i;}
}
pct aux;
aux=P[i1];
P[i1]=P[1];
P[1]=aux;
sort(P+2,P+N+1,cmp);
P[++N]=P[1];
infas();
g<<k-1<<'\n';
for (int i=2;i<=k;i++)
g<<setprecision(6)<<fixed<<P[st[i]].x<<" "<<P[st[i]].y<<'\n';
return 0;
}