Pagini recente » Cod sursa (job #1312335) | Cod sursa (job #1060535) | Cod sursa (job #2694716) | Cod sursa (job #2505475) | Cod sursa (job #2430297)
#include <iostream>
#include <fstream>
#include <queue>
#include <cmath>
#define NMAX 120005
#define inf 2147000000
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
int st[NMAX], P, N, k;
pair<double, double> M[NMAX];
class comp{
public:
bool operator()(int a, int b){
int y1, y2, x1, x2;
y1 = M[a].second - M[P].second;
y2 = M[b].second - M[P].second;
x1 = M[a].first - M[P].first;
x2 = M[b].first - M[P].first;
return !(y1*x2 < y2*x1);
}
};
priority_queue<int, vector<int>, comp> pq;
void read()
{
double ymin = 1000000001, xmin = 1000000001;
fin >> N;
for(int i = 1; i <= N; i++){
fin >> M[i].first >> M[i].second;
if(M[i].first < xmin)
xmin = M[i].first, ymin = M[i].second, P = i;
else if(M[i].second == xmin && M[i].first < ymin)
ymin = M[i].second, P = i;
}
}
void SlopeSort()
{
double x, y;
for(int i = 1; i <= N; i++){
if(i == P) continue;
pq.push(i);
}
}
bool convex(){
int x1, x2, x3, y1, y2, y3;
x1 = M[st[k - 2]].first, y1 = M[st[k - 2]].second;
x2 = M[st[k - 1]].first, y2 = M[st[k - 1]].second;
x3 = M[st[k - 0]].first, y3 = M[st[k - 0]].second;
return (x2 - x1)*(y3 - y1) - (y2 - y1)*(x3 - x1) > 0;
}
int main()
{
read();
SlopeSort();
k = 2; st[1] = P; st[2] = pq.top(); pq.pop();
while(!pq.empty()){
st[++k] = pq.top(); pq.pop();
while(!convex()){
st[--k] = st[k + 1]; st[k + 1] = 0;
}
}
fout << k << "\n";
for(int i = 1; i <= k; i++) fout << M[st[i]].first << " " << M[st[i]].second << "\n";
return 0;
}