Pagini recente » Cod sursa (job #2334969) | Cod sursa (job #1128747) | Cod sursa (job #1336853) | Cod sursa (job #2116914) | Cod sursa (job #1009775)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>
#define oo 1<<15
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
pair<double,double>points[120100];
pair<double,double> minPoint;
int n;
stack< pair<double,double> >hull;
double panta(pair<double,double> A, pair<double,double> B){
if(A.first == B.first)
return oo;
return (B.second - A.second) / (B.first - A.first);
}
bool cmp(pair<double,double> A, pair<double,double> B){
return panta(minPoint,A) < panta(minPoint,B);
}
void scan(){
fin >> n;
int position = 0;
for(int i =0 ; i < n; i++){
double x,y;
fin >> x >> y;
points[i].first = x;
points[i].second = y;
if(i == 0)
minPoint = points[0];
else
if(points[i].first < minPoint.first || (points[i].first == minPoint.first) && (points[i].second < minPoint.second))
{
minPoint = points[i];
position = i;
}
}
points[position] = points[n-1];
n--;
points[n].first = 0;
points[n].second =0;
sort(points,points+n,cmp);
}
double getDeterminate(pair<double, double> p1, pair<double, double> p2, pair<double, double> p3){
return (p1.first * p2.second) + (p3.first * p1.second) + (p2.first * p3.second) -
(p2.second * p3.first) - (p3.second * p1.first) - (p1.second * p2.first);
}
void createHull(){
hull.push(minPoint);
hull.push(points[0]);
for(int i = 1; i < n;i++){
pair <double, double> p1,p2,p3;
p3 = points[i];
p2 = hull.top();
hull.pop();
p1 = hull.top();
hull.pop();
if(getDeterminate(p1,p2,p3) >= 0){
hull.push(p1);
hull.push(p2);
hull.push(p3);
}
else{
while(getDeterminate(p1,p2,p3) < 0)
{
p2 = p1;
p1 = hull.top();
hull.pop();
}
hull.push(p1);
hull.push(p2);
hull.push(p3);
}
}
}
void printHull(){
fout << hull.size() << endl;
fout << std::fixed;
while(!hull.empty()){
fout << std::setprecision(6) << hull.top().first << " " << hull.top().second << setprecision(2) << endl;
hull.pop();
}
}
int main()
{
scan();
createHull();
printHull();
return 0;
}