Pagini recente » jc2020/clasament | Cod sursa (job #1903998) | Cod sursa (job #507049) | Cod sursa (job #2265018) | Cod sursa (job #3212538)
#include <bits/stdc++.h>
#define NMAX 120000
#define ll unsigned long long
#define MOD 1000000007
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct pt
{
double x,y;
} points[NMAX+1];
int n;
double det(pt a,pt b,pt c)
{
return (b.y-a.y)*(c.x-b.x) - (b.x-a.x)*(c.y-b.y);
}
bool cmp(pt a,pt b)
{
return det(points[1],a,b) < 0;
}
vector<pt> S;
int main()
{
fin >> n;
for(int i=1;i<=n;i++)
{
fin >> points[i].x >> points[i].y;
}
int start=1;
for(int i=2;i<=n;i++)
{
if(points[i].y < points[start].y || (points[i].y==points[start].y && points[i].x < points[start].x))
{
start=i;
}
}
swap(points[start],points[1]);
sort(points+2,points+n+1,cmp);
for(int i=1;i<=2;i++)
{
S.push_back(points[i]);
}
for(int i=3;i<=n;i++)
{
while(S.size() >= 2 && det(S[S.size()-2],S[S.size()-1],points[i]) >= 0)
{
S.pop_back();
}
S.push_back(points[i]);
}
fout << S.size() << "\n";
for(auto i : S)
{
fout << setprecision(6) << fixed << i.x << " " << i.y << "\n";
}
}