Cod sursa(job #2019695)

Utilizator AndreosAndrei Otetea Andreos Data 8 septembrie 2017 12:43:25
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const double eps=10e-12;
struct POINT
{
    double x,y;
};
double dist(POINT p1,POINT p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double cp(POINT p1,POINT p2,POINT p3)
{
    return (p2.x-p1.x)*(p3.y-p2.y)-(p2.y-p1.y)*(p3.x-p2.x);
}
int ccw(POINT p1,POINT p2,POINT p3)
{
    double c;
    c=cp(p1,p2,p3);
    if(fabs(c)<eps)
        return 0;
    if(c>=eps)
        return 1;
    return -1;
}
POINT ll;
bool cmp(POINT p1,POINT p2)
{
	int c=ccw(ll,p1,p2);
	if(c==1)
		return 1;
	if(c==-1)
		return 0;
	double d1,d2;
	d1=dist(ll,p1);
	d2=dist(ll,p2);
	if(d1-d2<eps)
		return 1;
	if(d1-d2>=eps)
		return 0;
}
vector <POINT> P;
vector <int> h;
int main()
{
    freopen("infasuratoare.in","r",stdin);
    freopen("infasuratoare.out","w",stdout);
    int n,i,id,top;
    double px,py;
    POINT now;
    scanf("%d",&n);
    now.x=now.y=0;
    P.push_back(now);
    for(i=1;i<=n;++i)
    {
    	scanf("%lf%lf",&px,&py);
    	now.x=px;
    	now.y=py;
    	if((i==1) || ((ll.y==py && ll.x>px) || (ll.y>py)))
		{
			ll.x=px;
			ll.y=py;
			id=i;
		}
		P.push_back(now);
    }
    P.erase(P.begin()+id);
    P[0]=ll;
    sort(P.begin()+1,P.end(),cmp);
    P.push_back(ll);
    h.push_back(0);
    h.push_back(1);
    i=2;
    while(i<=n)
    {
    	if(ccw(P[h[h.size()-2]],P[h[h.size()-1]],P[i])>0)
    	{
    		h.push_back(i);
    		i++;
    	}
    	else
			h.pop_back();
    }
    printf("%d\n",h.size()-1);
    for(i=0;i<=h.size()-2;++i)
    {
    	now=P[h[i]];
    	printf("%f %f\n",now.x,now.y);
    }
    return 0;
}