Pagini recente » Cod sursa (job #2759832) | Cod sursa (job #7199) | Cod sursa (job #689616) | Cod sursa (job #1810106) | Cod sursa (job #1395357)
#include<iostream>
#include<fstream>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;
#define NMAX 100001
#define INF (1<<30)
#define eps 0.0000000001
struct punct {
double x,y;
punct() {
x=0;
y=0;
}
punct(double _x, double _y) {
x=_x;
y=_y;
}
};
inline double cross_product(punct a, punct b, punct c)
{
return (double)(b.x-a.x)*(c.y-a.y)-(double)(c.x-a.x)*(b.y-a.y);
}
struct cmp {
bool operator () (const punct &a, const punct &b) const {
if(fabs(a.x-b.x)<=eps)
return true;
else return a.x<b.x;
}
};
punct v[NMAX],sus[NMAX],jos[NMAX];
int main ()
{
int i,n,n1,n2,k;
double s,j,maxy,miny;
punct a,b,c,q;
ifstream f("infasuratoare.in");
ofstream g("infasuratoare.out");
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
f.close();
sort(v+1,v+n+1,cmp());
n1=n2=0;
k=0;
s=0;
while(k+1<=n) {
k++;
j=v[k].x;
maxy=v[k].y;
miny=v[k].y;
while(fabs(v[k+1].x-j)<=eps && k+1<=n) {
k++;
maxy=max(maxy,v[k].y);
miny=min(miny,v[k].y);
}
while(n1>=2 && cross_product(sus[n1-1],sus[n1],punct(j,maxy))>0) {
s=s+(double)fabs(cross_product(sus[n1-1],sus[n1],punct(j,maxy)))/2.0;
n1--;
}
while(n2>=2 && cross_product(jos[n2-1],jos[n2],punct(j,miny))<0) {
s=s+(double)fabs(cross_product(jos[n2-1],jos[n2],punct(j,miny)))/2.0;
n2--;
}
sus[++n1]=punct(j,maxy);
jos[++n2]=punct(j,miny);
}
k=1;
if(fabs(sus[1].x-jos[1].x)<=eps && fabs(sus[1].y-jos[1].y)<=eps)
k=2;
if(fabs(sus[n1].x-jos[n2].x)<=eps && fabs(sus[n1].y-jos[n2].y)<=eps)
n1--;
g<<n1+n2-k+1<<'\n';
for(i=1;i<=n2;i++) {
g<<fixed;
g<<setprecision(6)<<jos[i].x<<" "<<jos[i].y<<'\n';
}
for(i=n1;i>=k;i--) {
g<<fixed;
g<<setprecision(6)<<sus[i].x<<" "<<sus[i].y<<'\n';
}
g.close();
return 0;
}