Pagini recente » Cod sursa (job #2235715) | Cod sursa (job #1769442) | Cod sursa (job #385752) | Cod sursa (job #2190223) | Cod sursa (job #2406616)
#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 ;
return 1;
}
int main()
{
double x , y , xmin= 1000000001, 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 = 1 ; i <= n ; i++ )
cout << pct[i].first << " " << pct[i].second << endl ;
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]) ;
continue ;
}
while ( ar < 0 )
{
vv.pop_back() ;
ar = faria(vv[vv.size()-2],vv[vv.size()-1],pct[i]) ;
}
vv.push_back(pct[i]) ;
}
fout << vv.size() << '\n' ;
for ( auto vec : vv )
fout << setprecision(12) << vec.first << " " << vec.second << '\n' ;
}