Cod sursa(job #2106004)

Utilizator AndreiStanescuAlloys Nokito AndreiStanescu Data 14 ianuarie 2018 19:12:01
Problema Infasuratoare convexa Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 6.39 kb
//Volum
/*#include<bits/stdc++.h>
#define N 755
using namespace std;

int a[N][N],n,m;

unsigned long long answer;

typedef struct LM{int cost,l,c;};


typedef struct cmpdst
{
    bool operator() (LM x, LM y)
    {
        return x.cost>y.cost;
    }
};

priority_queue <LM, vector<LM> , cmpdst> q;

pair<int,int> q2[N*N];

int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
bool viz[N][N],sel[N][N];

void read()
{
    int i,j;
    LM cel;
    freopen("volum.in","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
        scanf("%d",&a[i][j]);

    for(i=1;i<=n;i++)
    {
        cel.cost=a[i][1];
        cel.l=i;
        cel.c=1;
        q.push(cel);

        cel.cost=a[i][m];
        cel.l=i;
        cel.c=m;
        q.push(cel);

        viz[i][1]=viz[i][m]=1;
    }
    for(i=2;i<=m;i++)
    {
       cel.cost=a[1][i];
        cel.l=1;
        cel.c=i;
        q.push(cel);

        cel.cost=a[n][i];
        cel.l=n;
        cel.c=i;
        q.push(cel);

        viz[i][1]=viz[i][m]=1;
        viz[1][i]=viz[n][i]=1;

    }
}

void dijkstra()
{
    int p,u,i,j,high,x,y,xu,yu;
    LM cel;

    while(!q.empty())
    {
        p=u=1;
        q2[u]=make_pair(q.top().l,q.top().c); //coordonatele punctului ales
        sel[q.top().l][q.top().c]=1;
        high=q.top().cost;
        while(p<=u)
        {
            x=q2[p].first;
            y=q2[p].second;
            p++;
            for(j=0;j<4;j++)
            {
                xu=x+dx[j];
                yu=y+dy[j];
                if(xu<1 || xu>n || yu<1 || yu>m) continue;
                if(sel[xu][yu]) continue;
                if(a[xu][yu]<=high)
                {
                    answer+=(high-a[xu][yu])*1ll;
                    //cout<<answer<<endl;
                    q2[++u]=make_pair(xu,yu);
                    sel[xu][yu]=1;
                }
                else
                {
                    if(viz[xu][yu]) continue;
                    cel.cost=a[xu][yu],cel.l=xu,cel.c=yu;
                    q.push(cel);
                    viz[xu][yu]=1;
                }

            }
        }
          q.pop();

    }


}

int main()
{
    read();
    dijkstra();
    freopen("volum.out","w",stdout);
    cout<<answer;
}*/


//cezar-oji 2007
/*#include<bits/stdc++.h>
using namespace std;
const int N=10005;
short grad[N],cost[N];
int n,k;

typedef struct cmpdst
{
    bool operator() (short x,short y)
    {
        return cost[x]>cost[y];
    }
};

priority_queue <short, vector<short> , cmpdst> q;

vector <short> G[N];
bool viz[N];
int ans;

void read()
{
    int i,x,y;
    freopen("cezar.in","r",stdin);
    scanf("%d%d",&n,&k);

    for(i=1;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }

    for(i=1;i<=n;i++)
    {
        grad[i]=G[i].size();
        cost[i]=1;
        if(grad[i]==1)
            {q.push(i);
            viz[i]=1;
            } //la inceput toate au acelasi cost oricum...
    }
}
  void mingrad(); //nu mai e nevoie, caci fiind n-1 muchii si n noduri, asa ca
                    //mereu va exista un nod cu gradul 1, acela dupa ce va fi sters
                    //n-- si dem. se repeta si din nou va exista un nod cu gradul 1
                    //qed, hai ca a mers matematic simplu :)
void elimin()
{
    int x,y,u,j,i;
    for(i=1;i<=n-k-1;i++)
       { x=q.top();   //x reprezinta asezarea de cost minim cu grad 1
        q.pop();
        ans+=cost[x];
        grad[x]=0;
        for(j=0;j<G[x].size();j++)
        {
            u=G[x][j];
            if(grad[u])
            {
                grad[u]--;
                cost[u]+=cost[x];

            }
           // if(grad[u]==1) q.push(u);  //prin Inductie, adaugam gradele nodurilor modificate
        }
        //sort(u+1,u+n+1);
       for(j=1;j<=n;j++) if(grad[j]==1 && !viz[j])
       {q.push(j);
       viz[j]=1;
       }
       }
}



int main()
{
    read();
    elimin();
    freopen("cezar.out","w",stdout);
    cout<<ans;

}*/
//infasuratoare convexa
#include<bits/stdc++.h>
using namespace std;
const int N=120005;
const double eps=1e-12;
int n;
double x[N],y[N];
typedef pair<double,double> punct;
punct v[N];
void read()
{
    int i;
    ifstream fin("infasuratoare.in");
    fin>>n;
    for(i=1;i<=n;i++)  {fin>>x[i]>>y[i];
    v[i].first=y[i];
    v[i].second=x[i];
    }

}


void qsort(int st, int dr)
{
int i,j,mx,my,ax,aux;
i=st; j=dr; my=y[(st+dr)/2]; mx=x[(st+dr)/2];
do
{
while((y[i]<my)||((y[i]==my)&&(x[i]<mx))) i++;
while((y[j]>my)||((y[j]==my)&&(x[j]>mx))) j--;
if(i<=j)
{

aux=x[i];x[i]=x[j];x[j]=aux;
aux=y[i];y[i]=y[j];y[j]=aux;

i++;
j--;
}
} while(i<=j);
if(st<j) qsort(st, j);
if(i<dr) qsort(i, dr);
}

int orient(int x1,int y1,int x2,int y2,int x3,int y3)
{
    //stabileste sensul
    //if(asin(x1/y1)<asin(x2/y2) && asin(x2/y2)<asin(x3,y3)) return -1;
    int det1,det2,sup,trig;
    det1=x1*y2+x2*y3+x3*y1;
    det2=y1*x2+y2*x3+y3*x1;
    sup=det1-det2;
    //abs(sup)/2 e aria
    if(sup<0) trig=-1;
    else if(sup>0) trig=1;
    else trig=0;
    return trig;
}

void graham()
{
    int i,vf=0;
    bool liber[N];
   int st[N];
    for(i=1;i<=n;i++) liber[i]=true;
    st[1]=1;
    st[2]=2;
    liber[1]=liber[2]=false;
    vf=2;

    for(i=3;i<=n;i++)       //incerc sa completez prin stanga
    {
        while(vf>=2 && abs(orient(x[st[vf-1]], y[st[vf-1]],x[st[vf]],y[st[vf]], x[i],y[i])+1)<eps)
        {
            //daca sunt in sens invers trigonometric le extrag din stiva
            liber[st[vf]]=true;
            vf--;
        }
        vf++;
        st[vf]=i;
        liber[i]=false;
    }

    for(i=n-1;i>=1;i--)       //incerc prin dreapta
        if(liber[i])
    {
        //vs=vf;
        while(vf>=2 && abs(orient(x[st[vf-1]],y[st[vf-1]],x[st[vf]],y[st[vf]],x[i],y[i])+1)<eps)
            liber[st[vf--]]=true;
        st[++vf]=i;
        liber[i]=false;
    }
    freopen("infasuratoare.out","w",stdout);
cout<<vf<<endl;
for(i=1;i<=vf;i++) cout<<fixed<<setprecision(6)<<x[st[i]]<<' '<<y[st[i]]<<endl;

}

int main()
{
    read();
    //qsort(1,n);
    sort(v+1,v+n+1);
    for(int i=1;i<=n;i++)
    {
        y[i]=v[i].first;
        x[i]=v[i].second;
    }
    graham();

}