Pagini recente » Cod sursa (job #2327894) | Cod sursa (job #2523596) | Cod sursa (job #128106) | Cod sursa (job #228396) | Cod sursa (job #1076712)
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
struct Coordonate
{
double x,y;
}Puncte[120500];
int N;
int Viz[120500];
vector <int> S;
ifstream f("infasuratoare.in");
ofstream fout("infasuratoare.out");
int cmp(Coordonate A, Coordonate B)
{
return A.y<B.y || A.y==B.y && A.x<B.x;
}
void Citire()
{
f>>N;
for(int i=1;i<=N;++i)
f>>Puncte[i].x>>Puncte[i].y;
sort(Puncte+1,Puncte+N+1,cmp);
}
double Det(Coordonate A, Coordonate B, Coordonate C)
{
return A.x*B.y+B.x*C.y+A.y*C.x-B.y*C.x-A.x*C.y-A.y*B.x;
}
void Rezolvare()
{
S.push_back(1);
S.push_back(2);
Viz[2]=1;
double R;
for(int i=3;i<=N;++i)
{
R=Det(Puncte[S[S.size()-2]],Puncte[S[S.size()-1]],Puncte[i]);
while(R<0)
{
if(S.size()<=2)
{
Viz[S.back()]=0;
S.pop_back();
break;
}
Viz[S.back()]=0;
S.pop_back();
R=Det(Puncte[S[S.size()-2]],Puncte[S[S.size()-1]],Puncte[i]);
}
S.push_back(i);
Viz[i]=1;
}
for(int i=N;i>=1;--i)
{
if(!Viz[i])
{
R=Det(Puncte[S[S.size()-2]],Puncte[S[S.size()-1]],Puncte[i]);
while(R<0)
{
if(S.size()<=2)
S.pop_back();
S.pop_back();
R=Det(Puncte[S[S.size()-2]],Puncte[S[S.size()-1]],Puncte[i]);
}
S.push_back(i);
}
}
}
int main()
{
Citire();
Rezolvare();
fout<<S.size()<<"\n";
for(int i=0;i<S.size();++i)
fout<<Puncte[S[i]].x<<" "<<Puncte[S[i]].y<<"\n";
f.close();
fout.close();
return 0;
}