Pagini recente » Cod sursa (job #1099681) | Cod sursa (job #1771413) | Cod sursa (job #2036283) | Cod sursa (job #2985622) | Cod sursa (job #1096641)
#include <fstream>
#include <algorithm>
#include <stack>
#include <iomanip>
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
double x, y;
};
punct a[120001];
stack<punct> S;
stack<punct> AUX;
punct refp;
bool cmp(punct A, punct B)
{
return (A.y-refp.y)*(B.x-refp.x) < (B.y-refp.y)*(A.x-refp.x);
}
int rotation(punct A, punct B, punct C)
{
if(A.x == refp.x && A.y == refp.y )
return true;
if(B.y == refp.y && B.x == refp.x )
return false;
return (C.y - A.y)*(B.x - A.x) - (C.x - A.x) * (B.y - A.y);
}
int main()
{
int n;
refp.x = 1000000000;
refp.y = 1000000000;
fin>>n;
for(int i=1;i<=n;i++)
{
fin>>a[i].x>>a[i].y;
if(a[i].y < refp.y || (a[i].y < refp.y && a[i].x < refp.x ))
refp = a[i];
}
sort(a+1,a+1+n,cmp);
S.push(refp);
S.push(a[2]);
//S.push(a[3]);
for(int i=3;i<=n;i++)
{
bool gata;
do
{
gata = true;
punct y = S.top();
S.pop();
punct x = S.top();
if(rotation(x,y,a[i]) < 0)
{
gata = false;
}
else
{
S.push(y);
}
}while(!gata && S.size() >= 3);
S.push(a[i]);
}
fout<<S.size()<<'\n';
while(!S.empty())
{
AUX.push(S.top());
S.pop();
}
while(!AUX.empty())
{
punct p = AUX.top();
fout<<setprecision(6)<<fixed<<p.x<<' '<<p.y<<'\n';
AUX.pop();
}
fin.close();
fout.close();
return 0;
}