Pagini recente » Cod sursa (job #1075129) | Cod sursa (job #1278461) | Cod sursa (job #1916069) | Cod sursa (job #283896) | Cod sursa (job #1343652)
#include <cstdio>
#include <vector>
#include <algorithm>
#define nmax 1000
using namespace std;
FILE *f1=fopen("infasuratoare.in","r"),*f2=fopen("infasuratoare.out","w");
struct punct
{
double x,y;
}p0;
vector <punct> plan;
punct inf[nmax];
int n,vf;
double produs(punct a,punct b,punct c)
{
return ((c.y-a.y)*(b.x-a.x)-(b.y-a.y)*(c.x-a.x));
}
bool comp(punct a,punct b)
{
return produs(p0,a,b)>0;
}
void push(punct a)
{
vf++;
inf[vf]=a;
}
void pop()
{
vf--;
}
int main()
{
fscanf(f1,"%d",&n);
for(;n;n--)
{
punct b;
fscanf(f1,"%lf%lf",&b.x,&b.y);
plan.push_back(b);
}
p0.x=plan[0].x;
p0.y=plan[0].y;
int i,a=0;
punct aux;
for(i=0;i<plan.size();i++)
if(plan[i].x<p0.x || plan[i].x==p0.x&&plan[i].y<p0.y)
{
p0.x=plan[i].x;
p0.y=plan[i].y;
a=i;
}
aux=plan[0];
plan[0]=plan[a];
plan[a]=aux;
sort(plan.begin()+1,plan.end(),comp);
push(plan[0]);
push(plan[1]);
double o=0;
for(i=2;i<plan.size();i++)
{
o=produs(inf[vf-1],inf[vf],plan[i]);
if(o==0)
{
pop();
push(plan[i]);
}
else if(o>0)push(plan[i]);
else
{
while(o<=0 && vf>1)
{
pop();
o=produs(inf[vf-1],inf[vf],plan[i]);
}
push(plan[i]);
}
}
fprintf(f2,"%d\n",vf);
for(i=1;i<=vf;i++)
fprintf(f2,"%0.6f %0.6f\n",inf[i].x,inf[i].y);
fclose(f1);
fclose(f2);
return 0;
}
//Our greatest weakness lies in giving up. The most certain way to succeed is always to try just one more time.