Pagini recente » Cod sursa (job #2122752) | Cod sursa (job #1265916) | Cod sursa (job #710686) | Cod sursa (job #46103) | Cod sursa (job #729223)
Cod sursa(job #729223)
#include<fstream>
#include<vector>
#include<math.h>
#include<cstdio>
#include<algorithm>
#define pb push_back
#define mp make_pair
#define maxn 120010
#define inF "infasuratoare.in"
#define outF "infasuratoare.out"
using namespace std;
ifstream in(inF);
vector<pair<double,double> >vect;
int N,origine,v[maxn],coada[maxn];
bool cmp(int x,int y)
{
return (vect[x].first-vect[origine].first)*(vect[y].second-vect[origine].second)<(vect[y].first-vect[origine].first)*(vect[x].second-vect[origine].second);
}
long double unghi(int x, int y, int z)
{
return (long double)(vect[x].first*vect[y].second+vect[y].first*vect[z].second+vect[z].first*vect[x].second)-(long double)(vect[x].second*vect[y].first+vect[y].second*vect[z].first+vect[z].second*vect[x].first);
}
void read()
{
in>>N;
for(int i=0;i<N;i++)
{
double x,y;
in>>x>>y;
vect.pb(mp(x,y));
if(x<vect[origine].first || (x==vect[origine].first && y<vect[origine].second)) origine=i;
}
}
int main()
{
int i;
read();
for(i=1;i<=N;i++)
{
if(i==origine) continue;
v[++v[0]]=i;
}
sort(v+1,v+v[0]+1,cmp);
coada[++coada[0]]=origine;
for(i=1;i<=N;i++)
{
if(v[i]==origine) continue;
while(v[0]>=2 && unghi(coada[coada[0]-1],coada[coada[0]],v[i])>0) --coada[0];
coada[++coada[0]]=v[i];
}
freopen("infasuratoare.out","w",stdout);
printf("%d\n",coada[0]);
reverse(coada+1,coada+coada[0]+1);
for(i=1;i<=coada[0];i++)
{
printf("%lf %lf\n",vect[coada[i]].first,vect[coada[i]].second);
}
return 0;
}