Pagini recente » Cod sursa (job #2726448) | Cod sursa (job #1921583) | Cod sursa (job #1686552) | Cod sursa (job #425528) | Cod sursa (job #1608277)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <cstdio>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define point pair < double , double >
ifstream f("infasuratoare.in");
//ofstream g("infasuratoare.out");
vector < point > v;
point st[120001];
int n , top ;
float xx , yy;
double ecuatia_dreptei(const point &a , const point &b ,const point &c )
{
return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
bool comp ( const point &a , const point &b )
{
return ecuatia_dreptei(v[0],a,b)>0;
}
void citire_date()
{
f >> n ;
for ( ; n-- ; )
{
f >> xx >> yy;
v.pb(mp(xx,yy));
}
n = v.size();
}
void sortare_puncte()
{
int poz = 0;
for ( int i = 1; i < n ; i++ )
if ( v[i].second < v[poz].second )
poz = i;
else if ( v[i].second == v[poz].second and v[i].first < v[poz].first)
poz = i;
swap(v[0],v[poz]);
sort(v.begin()+1 , v.end() , comp );
}
void afis ( )
{
freopen("infasuratoare.out","w",stdout);
printf("%d\n",top);
for ( int i = top ; i >= 1; i-- )
printf("%.9f %.9f\n",st[i].x,st[i].y);
}
void infasuratoare_convexa()
{
sortare_puncte();
for ( int i = 0 ; i < n ; i++ )
{
while ( top >= 2 and ecuatia_dreptei( v[i],st[top],st[top-1]) > 0 ) top--;
st[++top] = v[i];
}
afis();
}
int main()
{
citire_date();
infasuratoare_convexa();
return 0;
}