Pagini recente » Cod sursa (job #3224472) | Cod sursa (job #2878741) | Cod sursa (job #525906) | Cod sursa (job #1651613) | Cod sursa (job #1355348)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point{
double x;
double y;
};
bool pointsort(Point A, Point B)
{
return(A.x<B.x||(A.x==B.x && A.y<B.y));
}
double cross(Point O, Point A, Point B)
{
return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
vector <Point> P;
int n;
int main() {
fin>>n;
for(int i=1; i<=n; ++i)
{
Point N;
fin>>N.x>>N.y;
P.push_back(N);
}
sort(P.begin(), P.end(), pointsort);
int k=0;
vector <Point> H(2*n);
for(int i=0; i<n; ++i)
{
while(k>=2&&cross(H[k-2], H[k-1], P[i])<=0)k--;
H[k++] = P[i];
}
for(int i=n-2, t=k+1; i>=0; i--) {
while(k>=t && cross(H[k-2], H[k-1], P[i])<=0)k--;
H[k++] = P[i];
}
fout<<--k<<"\n";
fout << setprecision(6) << fixed;
for(int i=1; i<k; ++i)
fout<<H[i].x<<" "<<H[i].y<<"\n";
}