Pagini recente » Cod sursa (job #2846239) | Cod sursa (job #961498) | Cod sursa (job #1657305) | Cod sursa (job #2684815) | Cod sursa (job #868688)
Cod sursa(job #868688)
#include <fstream>
#include <deque>
#include <algorithm>
#include <cmath>
#define patch 1000000000
using namespace std;
double ar(double x1, double y1, double x2, double y2, double x3, double y3) {
return (x1*y2-y1*x1+x2*y3-y2*x3+x3*y1-y3*x1);
}
struct pct{
double x,y;
};
pct v[120001];
deque <pct> inf;
int ind,o[120001],otmp[120001];
double tg[120001],xmn,ymn;
double dist(int i, int j) {
return sqrt( ((v[i].x-v[j].x)*(v[i].x-v[j].x)) + ((v[i].y-v[j].y)*(v[i].y-v[j].y)));
}
bool srt(int i, int j) {
if (i==ind)
return 1;
else if (j==ind)
return 0;
else if (tg[i]==tg[j])
return (dist(i,ind)<dist(j,ind));
else
return (tg[i]<tg[j]);
}
int n;
int main() {
int i;
xmn=ymn=2000000000;
ifstream in("infasuratoare.in");
ofstream out("infasuratoare.out");
in>>n;
for (i=1; i<=n; i++) {
in>>v[i].x>>v[i].y;
v[i].x+= patch;
v[i].y+= patch;
if (v[i].x<xmn) {
ind = i;
xmn=v[i].x;
ymn=v[i].y;
}
else if (v[i].x==xmn&&v[i].y<ymn) {
ind = i;
ymn=v[i].y;
}
o[i]=i;
}
for (i=1; i<=n; i++)
tg[i]=atan2(v[i].y-ymn,v[i].x-xmn );
sort(o+1,o+n+1,srt);
ind=n;
while (tg[o[ind]] == tg[o[ind-1]])
ind--;
for (i=ind; i<=n; i++)
otmp[i]=o[n-i+ind];
for (i=ind; i<=n; i++)
o[i]=otmp[i];
inf.push_back(v[o[1]]);
inf.push_back(v[o[2]]);
for (i=3; i<=n; i++) {
while (inf.size()>=2 && ar( inf[inf.size()-2].x,inf[inf.size()-2].y,inf[inf.size()-1].x,inf[inf.size()-1].y,v[o[i]].x,v[o[i]].y)<0)
inf.pop_back();
inf.push_back(v[o[i]]);
}
out.precision(15);
out<<inf.size()<<'\n';
for (i=0; i<inf.size(); i++)
out<<inf[i].x - patch<<' '<<inf[i].y-patch<<'\n';
out.close();
return 0;
}