Pagini recente » Cod sursa (job #2920641) | Cod sursa (job #816348) | Cod sursa (job #2808470) | Cod sursa (job #3193648) | Cod sursa (job #3270413)
#include <bits/stdc++.h>
#define db double
using namespace std;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
struct pct{
db x;
db y;
bool operator == (pct b){
if (x==b.x&&y==b.y)return 1;
}
void operator = (pct b){
x=b.x;
y=b.y;
}
}v[120004],*p0,s[120004];
long long n,i,j,cnt;
db det (pct a,pct b,pct c){
a.x-=c.x;
b.x-=c.x;
a.y-=c.y;
b.y-=c.y;
return double(b.x*a.y-b.y*a.x);
}
bool cmp(pct a,pct b){
return (det(a,b,*p0)<0);
}
int main()
{ f>>n;
for(i=1;i<=n;i++){
f>>v[i].x>>v[i].y;
if (i==1)p0=&v[i];
if (v[i].y<(*p0).y){
p0=&v[i];
}
if (v[i].y==(*p0).y&&(*p0).x<v[i].x){
p0=&v[i];
}
}
swap(*p0,v[1]);
sort(v+2,v+n+1,cmp);
//for (i=1;i<=n;i++){
// cout<<v[i].x<<' '<<v[i].y<<'\n';
//}
v[n+1]=*p0;
for (i=1;i<=n+1;i++){
while (cnt>=2){
db aux=det(v[i],s[cnt],s[cnt-1]);
if (aux<0)cnt--;
else break;
}
s[++cnt]=v[i];
}
cnt--;
g<<cnt<<'\n';
for (i=1;i<=cnt;i++){
g<<fixed<<setprecision(12)<<s[i].x<< ' ' <<s[i].y<<'\n';
}
//cout<<det({1,3},{3,1},{0,0});
return 0;
}