Pagini recente » Cod sursa (job #211964) | Cod sursa (job #215798) | Cod sursa (job #361983) | Cod sursa (job #183646) | Cod sursa (job #1110815)
#include <cstdio>
#include <iomanip>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<double,double> point;
FILE *f = fopen("infasuratoare.in","r");
FILE *g = fopen("infasuratoare.out","w");
int n, i, p;
int s[120005],h;
point v[120005], tmp;
int det(const point &a, const point &b, const point &c) {
if( (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) > 0)
return -1;
else
return 1;
}
bool cmp(const point &a, const point &b) {
if(det(v[1],a,b)==-1)
return 1;
return 0;
}
int main() {
fscanf(f,"%d",&n);
for(i=1;i<=n;i++)
fscanf(f,"%lf%lf",&v[i].x,&v[i].y);
p=1;
for(i=2;i<=n;i++)
if(v[i].y<v[p].y || (v[i].x==v[p].x && v[i].x<v[p].x) )
p=i;
tmp=v[p];
v[p]=v[1];
v[1]=tmp;
sort(v+2,v+n+1,cmp);
s[1]=1;
s[2]=2;
h=2;
for(i=3;i<=n;i++) {
while(h>=2 && det(v[s[h-1]],v[s[h]],v[i])==1)
h--;
s[++h]=i;
}
fprintf(g,"%d\n",h);
for(i=1;i<=h;i++)
fprintf(g,"%.6lf %.6lf\n", v[s[i]].x,v[s[i]].y);
return 0;
}