Pagini recente » Cod sursa (job #2210154) | Cod sursa (job #838520) | Cod sursa (job #1291037) | Cod sursa (job #260198) | Cod sursa (job #2988466)
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<double, double> pt;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct point
{
double x, y;
};
const int NMAX = 120000;
int n;
int pozrez[NMAX];
pair<double, double> arr[NMAX];
inline double det(pt a, pt b, pt c)
{
return (a.x*b.y + b.x*c.y + c.x*a.y - b.x*a.y - c.x*b.y - a.x*c.y);
}
inline bool Trig(const pair<double, double> &x, const pair<double, double> &y)
{
return det(arr[1], x, y) > 0;
}
inline void solution()
{
pt miniY = arr[1];
int minipos = 1;
for(int i = 1; i <= n; ++ i)
{
if(arr[i] < arr[minipos])
{
miniY = arr[i];
minipos = i;
}
}
swap(arr[1], arr[minipos]);
pozrez[1] = 1;
pozrez[2] = 2;
sort(arr + 2, arr + n + 1, Trig);
int k = 2;
for(int i = 3; i <= n; ++ i)
{
while(k > 1 && det(arr[pozrez[k-1]], arr[pozrez[k]], arr[i]) <= 0) k--;
pozrez[++k] = i;
}
fout << k << '\n';
for(int i = 1; i <= k; ++ i)
{
fout << arr[pozrez[i]].x << ' ' << arr[pozrez[i]].y << '\n';
}
}
int main()
{
ios::sync_with_stdio(false);
fin.tie(NULL);
fout.tie(NULL);
fin >> n;
for(int i = 1; i <= n; ++ i)
fin >> arr[i].x >> arr[i].y;
solution();
return 0;
}