Pagini recente » Cod sursa (job #2436238) | Cod sursa (job #592307) | Cod sursa (job #541257) | Cod sursa (job #1204148) | Cod sursa (job #1110326)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream fin ("infasuratoare.in");
ofstream fout ("infasuratoare.out");
struct punct {
double x;
double y;
}v[120010];
int i, p,s[120010],n;
double cmp (punct a, punct b) {
double ariec=a.x*b.y-b.x*a.y;
if (ariec<0)
return 0;
else
return 1;
}
int arie (int i, int j, int k) {
double ariec = (v[j].x-v[i].x)*(v[k].y-v[i].y)-(v[k].x-v[i].x)*(v[j].y-v[i].y);
if (ariec<0.000000000001)
return 1;
else
return 0;
}
int main () {
fin>>n;
for (i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort (v+1,v+n+1,cmp);
s[1]=1;
s[2]=2;
p=2;
for (i=3;i<=n;i++) {
while( arie (s[p-1],s[p],i) && p>=1 )
p--;
s[++p]=i;
}
fout<<p<<"\n";
fout << setprecision(6) << fixed;
for (i=1;i<=p;i++)
fout<<v[s[i]].x<<" "<<v[s[i]].y<<"\n";
return 0;
}