Pagini recente » Cod sursa (job #3226620) | Cod sursa (job #2602336) | Cod sursa (job #1927264) | Cod sursa (job #2917550) | Cod sursa (job #2724084)
#include<fstream>
#include<vector>
#include<cmath>
#include<algorithm>
#define pi 3.14159265359
using namespace std;
ifstream fin("infasuratoare.in");
ofstream fout("infasuratoare.out");
struct qwerty{
double x,y;
}a,mn;
int i,j,n,m;
vector <qwerty>x;
vector <qwerty>z;
bool unghi(qwerty a,qwerty b,qwerty c){
double arie = (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
if(arie<0)
return true;
return false;
}
void pr1(){
z.push_back(mn);
z.push_back(x[0]);
for(int i=1,size=x.size();i<size;i++){
while(!unghi(z[z.size()-1],z[z.size()-2],x[i]))
z.pop_back();
z.push_back(x[i]);
}
}
bool cum(qwerty a,qwerty b){
return atan2(mn.y-a.y,mn.x-a.x)<atan2(mn.y-b.y,mn.x-b.x);
}
int main(){
fin>>n;
fin>>mn.x>>mn.y;
for(i=2;i<=n;i++){
fin>>a.x>>a.y;
if(a.y==mn.y)
if(a.x<mn.x)
x.push_back(mn),mn=a;
else
x.push_back(a);
else
if(a.y<mn.y)
x.push_back(mn),mn=a;
else
x.push_back(a);
}
sort(x.begin(),x.end(),cum);
pr1();
fout<<z.size()<<'\n';
for(i=0;i<z.size();i++)
fout<<z[i].x<<' '<<z[i].y<<'\n';
return 0;
}