Pagini recente » Cod sursa (job #2786806) | Cod sursa (job #766660) | Cod sursa (job #2085552) | Cod sursa (job #1161630) | Cod sursa (job #1917406)
#include <bits/stdc++.h>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
#define punct pair<double,double>
#define x first
#define y second
vector < punct > v;
punct mn;
int n,ind;
double det(punct a, punct b, punct c)
{
return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
}
bool cmp(punct a,punct b)
{
return det(v[1],a,b)<0;
}
int main()
{
f>>n;
v= vector< punct >(n+1);
f>>mn.x>>mn.y;
v[1].x=mn.x;
v[1].y=mn.y;
for(int i=2;i<=n;i++)
{ f>>v[i].x>>v[i].y;
if(mn.x>v[i].x or(mn.x==v[i].x and mn.y>v[i].y))
{
mn=v[i];
ind=i;
}
}
swap(v[1],v[ind]);
sort(v.begin()+2,v.end(),cmp);
int head=2;
punct st[n+1];
st[1]=v[1];
st[2]=v[2];
for ( int i = 3; i <= n ; i++ )
{
while(head>=2 and det(v[i],st[head-1],st[head])>0 ) head--;
st[++head]=v[i];
}
freopen("infasuratoare.out","w",stdout);
printf("%d\n",head);
for ( int i = head; i>=1;i--)
{
printf("%.8f %.8f\n" , st[i].x , st[i].y) ;
}
}