Pagini recente » Cod sursa (job #1897280) | Cod sursa (job #1268502) | Cod sursa (job #2305480) | Cod sursa (job #1364324) | Cod sursa (job #1857090)
#include<fstream>
#include<algorithm>
#include<iomanip>
#define NMax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct Point
{
double x,y;
};
int N,Top;
Point V[NMax],S[NMax];
void Read()
{
fin>>N;
for(int i = 1 ; i <= N ; ++i)
fin>>V[i].x>>V[i].y;
}
double Area(Point A,Point B,Point C)
{
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
bool Comp(Point A,Point B)
{
return (Area(V[1],A,B) < 0);
}
void Solve()
{
int pos = 1;
for(int i = 2 ; i <= N ; ++i)
if(V[i].y < V[pos].y || (V[i].y == V[pos].y && V[i].x < V[pos].x))
pos = i;
swap(V[1],V[pos]);
sort(V+2,V+N+1,Comp);
S[1] = V[1];
S[2] = V[2];
Top = 2;
for(int i = 3 ; i <= N ; ++i)
{
while(Top >= 2 && Area(S[Top - 1],S[Top],V[i]) > 0)
Top--;
S[++Top] = V[i];
}
}
void Print()
{
fout<<Top<<"\n";
fout<<fixed<<setprecision(6)<<S[1].x<<" "<<S[1].y<<"\n";
for(int i = Top ; i >= 2 ; --i)
fout<<fixed<<setprecision(6)<<S[i].x<<" "<<S[i].y<<"\n";
}
int main()
{
Read();
Solve();
Print();
fin.close();
fout.close();
return 0;
}