Pagini recente » Cod sursa (job #2278422) | Cod sursa (job #619362) | Cod sursa (job #1027935) | Cod sursa (job #1568980) | Cod sursa (job #2935376)
#include <bits/stdc++.h>
#define NMAX 120002
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct punct
{
long double x;
long double y;
}p[NMAX];
enum Orientare
{
CLOCKWISE,
COUNTERCW,
COLINIARE
};
Orientare orientare(punct A, punct B, punct C)
{
long double det=(A.y-B.y)*(C.x-B.x)-(A.x-B.x)*(C.y-B.y);
if(det<0) return CLOCKWISE;
if(det>0) return COUNTERCW;
return COLINIARE;
}
bool comp(punct A, punct B)
{
if(A.x==B.x)
{
return (B.y>A.y);
}
else return (B.x>A.x);
}
int n;
vector <punct> v1;
vector <punct> v2;
void jum1()
{
v1.push_back(p[0]);
v1.push_back(p[1]);
for(int i=2; i<n; i++)
{
v1.push_back(p[i]);
int s=v1.size()-1;
while(s>1 && orientare(v1[s-2], v1[s-1], v1[s])==CLOCKWISE)
{
v1.erase(v1.begin()+s-1);
s--;
}
}
}
void jum2()
{
v2.push_back(p[n-1]);
v2.push_back(p[n-2]);
for(int i=n-3; i>=0; i--)
{
v2.push_back(p[i]);
int s=v2.size()-1;
while(s>1 && orientare(v2[s-2], v2[s-1], v2[s])==CLOCKWISE)
{
v2.erase(v2.begin()+s-1);
s--;
}
}
}
int main()
{
fin>>n;
for(int i=0; i<n; i++)
{
fin>>p[i].x>>p[i].y;
}
sort(p, p+n, comp);
jum1();
jum2();
int s1=v1.size(), s2=v2.size();
fout<<s1+s2-2<<'\n';
for(int i=0; i<s1-1; i++)
{
fout<<fixed<<setprecision(6)<<v1[i].x<<" ";
fout<<fixed<<setprecision(6)<<v1[i].y<<'\n';
}
for(int i=0; i<s2-1; i++)
{
fout<<fixed<<setprecision(6)<<v2[i].x<<" ";
fout<<fixed<<setprecision(6)<<v2[i].y<<'\n';
}
return 0;
}