Pagini recente » Cod sursa (job #1355101) | Cod sursa (job #272616) | Cod sursa (job #1359906) | Cod sursa (job #1994169) | Cod sursa (job #1548008)
#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct point
{
double x;
double y;
}
P[120001],first,S[120001];
int pos,top,N;
double det(point p1, point p2, point p3)
{
return (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
}
int cmp(point p1,point p2)
{
return det(P[1],p1,p2)>0;
}
int main()
{
f>>N;
f>>P[1].x>>P[1].y;
first=P[1];
pos=1;
for(int i=2;i<=N;i++){
f>>P[i].x>>P[i].y;
if(P[i].y<first.y || (P[i].y==first.y && P[i].x<first.x))
first=P[i],pos=i;
}
swap(P[1],P[pos]);
sort(P+2,P+N+1,cmp);
S[1]=P[1];
S[2]=P[2];
top=2;
for(int i=3;i<=N;i++){
while(top>=2 && det(S[top-1],S[top],P[i])<0)
top--;
S[++top]=P[i];
}
g<<top<<endl;
for(int i=1;i<=top;i++)
g<<setprecision(6)<<fixed<<S[i].x<<" "<<setprecision(6)<<fixed<<S[i].y<<endl;
}