Pagini recente » Cod sursa (job #8539) | Cod sursa (job #1187612) | Clasament Runda 1 | Cod sursa (job #1241182) | Cod sursa (job #1915122)
#include <bits/stdc++.h>
#define NMax 120005
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int N,Top;
struct Point { double x,y; } point[NMax],Stack[NMax];
double cross_product(Point a, Point b, Point c)
{
return a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-b.x*a.y-a.x*c.y;
}
bool sortComp(Point a,Point b)
{
return cross_product(point[1],a,b)<0;
}
int main()
{
fin>>N;
for(int i=1;i<=N;i++)
fin>>point[i].x>>point[i].y;
int pos=1;
for(int i=2;i<=N;i++)
if(point[i].x<point[pos].x)
pos=i;
swap(point[1],point[pos]);
sort(point+2,point+N+1,sortComp);
Stack[++Top]=point[1];
Stack[++Top]=point[2];
for(int i=3;i<=N;i++)
{
while(Top>=2 && cross_product(Stack[Top-1],Stack[Top],point[i])>0)
Top--;
Stack[++Top]=point[i];
}
fout<<Top<<"\n";
for(int i=Top;i>0;i--)
fout<<fixed<<setprecision(6)<<Stack[i].x<<" "<<Stack[i].y<<"\n";
return 0;
}