Cod sursa(job #1928336)

Utilizator GabiTulbaGabi Tulba-Lecu GabiTulba Data 16 martie 2017 01:10:52
Problema Infasuratoare convexa Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#define MaxN 120005
#define PI 3.141592
using namespace std;
 
FILE*IN,*OUT;
 
int N,Lower[MaxN],Upper[MaxN],UpSize=1,LowSize=1;
struct Point
{
    double x,y;
}v[MaxN];
bool cond(Point a,Point b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
double Angle(int x,int y)
{
        return atan2(v[x].y-v[y].y,v[x].x-v[y].x);
}
int main()
{
    IN=fopen("infasuratoare.in","r");
    OUT=fopen("infasuratoare.out","w");
 
    fscanf(IN,"%d",&N);
 
    for(int i=1;i<=N;i++)
        fscanf(IN,"%lf%lf",&v[i].x,&v[i].y);
    sort(v+1,v+1+N,cond);
    Lower[1]=Upper[1]=1;
    for(int i=2;i<=N;i++)
    {
        while(UpSize>1&&Angle(i,Upper[UpSize-1])-Angle(Upper[UpSize],Upper[UpSize-1])>0)
            UpSize--;
        Upper[++UpSize]=i;
        while(LowSize>1&&Angle(i,Lower[LowSize-1])-Angle(Lower[LowSize],Lower[LowSize-1])<0)
            LowSize--;
        Lower[++LowSize]=i;
    }
    fprintf(OUT,"%d\n",UpSize+LowSize-2);
    for(int i=1;i<=LowSize;i++)
        fprintf(OUT,"%lf %lf\n",v[Lower[i]].x,v[Lower[i]].y);
    for(int i=UpSize-1;i>1;i--)
        fprintf(OUT,"%lf %lf\n",v[Upper[i]].x,v[Upper[i]].y);
    return 0;
}