Cod sursa(job #3247716)

Utilizator Laurentiu_BTarabic Laurentiu Gabriel Laurentiu_B Data 8 octombrie 2024 21:31:24
Problema Infasuratoare convexa Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.06 kb
#include<bits/stdc++.h>
using namespace std;

int n,poz[200000],rez[200000],cnt=0;

stack<int> q;

struct twin{
    float x;
    float y;
};

bool compare(twin x,twin y)
{
    if(x.x==y.x)
        return x.y<y.y;
    else
        return x.x<y.x;
}

float det(float x1,float y1,float x2,float y2,float x3,float y3)
{
    return x1*y2+x2*y3+x3*y1-x2*y1-x3*y2-x1*y3;
}

twin a[200000];

int main()
{
    ifstream cin("infasuratoare.in");
    ofstream cout("infasuratoare.out");

    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i].x>>a[i].y;

    sort(a+1,a+n+1,compare);

    for(int i=2;i<n;i++)
        if(det(a[1].x,a[1].y,a[n].x,a[n].y,a[i].x,a[i].y)<0)
            poz[i]=1;

    q.push(1);

    for(int i=2;i<=n;i++)
        if(poz[i]||i==n)
        {
            int hold=q.top();
            q.pop();
            int x;

            if(q.size()>0)
             x=q.top();

            while(q.size()>1&&det(a[x].x,a[x].y,a[i].x,a[i].y,a[hold].x,a[hold].y)>0.0){
                hold=x;
                q.pop();
                if(!q.empty())
                x=q.top();
            }

            q.push(hold);
            q.push(i);
        }

    while(!q.empty())
    {
        if(!rez[q.top()])
            cnt++;
        rez[q.top()]=1;
        q.pop();
    }


    ///
    q.push(n);

    for(int i=n-1;i>=1;i--)
        if(!poz[i]||i==1)
        {
            int hold=q.top();
            q.pop();
            int x;

            if(q.size()>0)
             x=q.top();

            while(q.size()>1&&det(a[x].x,a[x].y,a[i].x,a[i].y,a[hold].x,a[hold].y)>0.0){
                hold=x;
                q.pop();
                if(!q.empty())
                x=q.top();
            }

            q.push(hold);
            q.push(i);
        }

    while(!q.empty())
    {
        if(!rez[q.top()])
            cnt++;
        rez[q.top()]=1;
        q.pop();
    }

    cout<<cnt<<endl;

    for(int i=1;i<=n;i++)
        if(rez[i])
            cout<<a[i].x<<" "<<a[i].y<<endl;

}