Pagini recente » Cod sursa (job #3289314) | Cod sursa (job #200147) | Cod sursa (job #713009) | Cod sursa (job #704296) | Cod sursa (job #2406585)
#include <bits/stdc++.h>
#define N 120005
using namespace std;
ifstream fin("infasuratoare.in") ;
ofstream fout("infasuratoare.out") ;
pair<double,double> pi , pct[N] ;
vector<pair<double,double> > vv;
bool cmp(pair<double,double> p1,pair<double,double> p2 )
{
return ((p1.second-pi.second)*(p2.first-pi.first)<(p1.first-pi.first)*(p2.second-pi.second)) ;
}
int faria (pair<double,double> p1 , pair<double,double> p2 , pair<double,double> p3 )
{
double aria = (p2.first-p1.first)*(p3.second-p1.second) - (p2.second-p1.second)*(p3.first-p1.first) ;
if ( aria < 0 )
return -1 ;
if ( aria == 0 )
return 0 ;
return 1;
}
int main()
{
double x , y , xmin , ymin = 1000000001 , ar;
int i , n ,id;
fin >> n ;
for ( i = 1 ; i <= n ; i++ )
{
fin >> x >> y ;
pct[i].first = x ;
pct[i].second = y ;
if ( y < ymin )
{
ymin = y ;
xmin = x;
pi.first = x ;
pi.second = y ;
id = i ;
}
if ( y == ymin )
{
if ( x < xmin )
{
x = xmin ;
pi.first = x ;
pi.second = y ;
id = i ;
}
}
}
swap(pct[1],pct[id]) ;
sort(pct+2,pct+n+1,cmp) ;
vv.push_back(pct[1]) ;
vv.push_back(pct[2]) ;
for ( i = 3 ; i <= n ; i++ )
{
ar = faria(vv[vv.size()-2],vv[vv.size()-1],pct[i]);
if ( ar > 0 )
vv.push_back(pct[i]) ;
if ( ar < 0 )
{
vv.pop_back() ;
vv.push_back(pct[i]);
}
}
fout << vv.size() << '\n' ;
for ( auto vec : vv )
fout << setprecision(12) << vec.first << " " << vec.second << '\n' ;
}