Pagini recente » Cod sursa (job #622371) | Cod sursa (job #2157192) | Cod sursa (job #1311176) | Cod sursa (job #2250686) | Cod sursa (job #2987265)
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
struct point {double x,y;};
ifstream fi("infasuratoare.in");
ofstream fo("infasuratoare.out");
int N;
point P[120001];
deque <int> DR;
deque <int> ST;
/// return 1 if and only if C is to the left of AB
int left(point A, point B, point C)
{
double det;
det=(B.x-A.x)*(C.y-A.y)-(C.x-A.x)*(B.y-A.y);
if (det>0)
return 1;
else
return 0;
}
int cmp(point A, point B)
{
if (A.y<B.y)
return 1;
if (A.y>B.y)
return 0;
return (A.x<B.x);
}
int main()
{
fi>>N;
for (int i=1;i<=N;i++)
fi>>P[i].x>>P[i].y;
sort(P+1,P+N+1,cmp);
/// DR is obtained
for (int i=1;i<=N;)
if (DR.size()<2)
{
DR.push_back(i);
i++;
}
else
{
int indA,indB;
point A,B;
indB=DR.back();
DR.pop_back();
indA=DR.back();
DR.pop_back();
A=P[indA];
B=P[indB];
if (left(A,B,P[i]))
{
DR.push_back(indA);
DR.push_back(indB);
DR.push_back(i);
i++;
}
else
DR.push_back(indA);
}
/// ST is obtained
for (int i=N;i>=1;)
if (ST.size()<2)
{
ST.push_back(i);
i--;
}
else
{
int indA,indB;
point A,B;
indB=ST.back();
ST.pop_back();
indA=ST.back();
ST.pop_back();
A=P[indA];
B=P[indB];
if (left(A,B,P[i]))
{
ST.push_back(indA);
ST.push_back(indB);
ST.push_back(i);
i--;
}
else
ST.push_back(indA);
}
ST.pop_front();
ST.pop_back();
fo<<DR.size()+ST.size()<<"\n";
for (auto it:DR)
fo<<P[it].x<<" "<<P[it].y<<"\n";
for (auto it:ST)
fo<<P[it].x<<" "<<P[it].y<<"\n";
fi.close();
fo.close();
return 0;
}