Pagini recente » Cod sursa (job #825450) | Cod sursa (job #2762180) | Cod sursa (job #2825015) | Cod sursa (job #2576295) | Cod sursa (job #965028)
Cod sursa(job #965028)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
struct Point
{
double x, y;
};
Point points[120005];
vector<Point> stive;
#define inf 1000000005.0
#define lng stive.size()-1
int N;
double dot_product(Point P0, Point P1, Point P2)
{
return (P1.x - P0.x)*(P2.y - P0.y) - (P2.x - P0.x)*(P1.y - P0.y);
}
bool cmp(Point P1, Point P2)
{
return dot_product(points[0],P1,P2) < 0;
}
int main()
{
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f >> N;
for(int i = 0; i < N; ++i)
{
f >> points[i].x >> points[i].y;
}
Point min;
min.x = 1000000005.0;
min.y = 1000000005.0;
for(int i = 0; i < N; ++i)
{
if( points[i].y < min.y || ( points[i].y == min.y && points[i].x < min.x))
{
min.x = points[i].x;
min.y = points[i].y;
}
}
swap(points[0],min);
sort(points+1, points+N, cmp);
stive.push_back(points[0]);
stive.push_back(points[1]);
for( int i=2; i<N; i++)
{
while(dot_product(stive[lng-1], stive[lng], points[i]) > 0)
{
stive.pop_back();
}
stive.push_back(points[i]);
}
g<<fixed<<stive.size()<<endl;
for(int i=lng; i>=0; i--)
g<<setprecision(9)<<stive[i].x<<" "<<stive[i].y<<" "<<endl;
return 0;
}