Pagini recente » Cod sursa (job #1778157) | Cod sursa (job #1662904) | Cod sursa (job #1840853) | Cod sursa (job #2402400) | Cod sursa (job #886071)
Cod sursa(job #886071)
#include<cstdio>
#include<cmath>
#include<algorithm>
#define pi 3.14159265358932
#define inf 2000000000
using namespace std;
struct pct{double x,y;}v[120006];
int n,i,ind[120006],st[120006],k,stp;
double xjos=inf,yjos=inf;
bool cmp(int i,int j)
{return (v[i].y-yjos)/(v[i].x-xjos)<(v[j].y-yjos)/(v[j].x-xjos);
}
bool semn(pct a,pct b,pct c)//returneaza semnul determinantului
{
return (a.x-b.x)*(b.y-c.y)<=(a.y-b.y)*(b.x-c.x);
}
int main()
{
freopen("infasuratoare.in","r",stdin);freopen("infasuratoare.out","w",stdout);
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
scanf("%lf %lf",&v[i].x,&v[i].y);
ind[i]=i;
if( v[i].x<xjos || (v[i].x==xjos && v[i].y<yjos) )
{
xjos=v[i].x;
yjos=v[i].y;
stp=i;
}//calculez punctul de extrem jos in stp
}
ind[1]=stp;
sort(ind+2,ind+n+1,cmp);
k=3; i=4; st[1]=stp; st[2]=ind[2]; st[3]=ind[3];
while(i<=n)
{
while( semn (v[st[k-1]] ,v[st[k]] ,v[ind[i]] ) ) k--;
st[++k]=ind[i++];
}
printf("%d\n",k);
for(i=1;i<=k;i++) printf("%lf %lf\n",v[st[i]].x,v[st[i]].y);
return 0;}