Submission #532637

#	Time	Username	Problem	Language	Result	Execution time	Memory
532637		stefantaga	Geometrija (COCI21_geometrija)	C++14	110 / 110	792 ms	7508 KiB

geometrija

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const double PI = acos(-1);
struct Punct
{
    long long x,y;
};
long long determinant (Punct a,Punct b,Punct c)
{
    return a.x*b.y+b.x*c.y+a.y*c.x-a.y*b.x-b.y*c.x-a.x*c.y;
}
bool compare (Punct a, Punct b)
{
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
ll n,i,st[4005],q,viz[4005];
Punct v[1005];
struct Triangle
{
    ll a,b,c;
};
ll ok[1005],primul;
vector <Triangle> triunghiuri;
long long ABS(long long x)
{
    if (x>0)
    {
        return x;
    }
    return -x;
}
bool sgn(ll x)
{
    if (x>=0)
    {
        return 1;
    }
    return 0;
}
bool seinter(pair <Punct,Punct> dreapta1,pair <Punct,Punct> dreapta2)
{
    ll det1=determinant(dreapta1.first,dreapta1.second,dreapta2.first);
    ll det2=determinant(dreapta1.first,dreapta1.second,dreapta2.second);
    ll det3=determinant(dreapta2.first,dreapta2.second,dreapta1.first);
    ll det4=determinant(dreapta2.first,dreapta2.second,dreapta1.second);

    if (!det1||!det2||!det3||!det4)
    {
        return 0;
    }
    if (sgn(det1)==sgn(det2))
    {
        return 0;
    }
    if (sgn(det3)==sgn(det4))
    {
        return 0;
    }
    return 1;
}
ll Marc[1005][1005],j;
vector <pair <int,int>> candidati;
Punct P;
bool compare2(int poz1, int poz2)
{
    Punct a,b;
    a=v[poz1];
    b=v[poz2];
    if (a.x - P.x >= 0 && b.x - P.x < 0)
        return true;
    if (a.x - P.x < 0 && b.x - P.x >= 0)
        return false;
    if (a.x - P.x == 0 && b.x - P.x == 0)
    {
        if (a.y - P.y >= 0 || b.y - P.y >= 0)
            return a.y > b.y;
        return b.y > a.y;
    }

    // compute the cross product of vectors (P -> a) x (P -> b)
    int det = (a.x - P.x) * (b.y - P.y) - (b.x - P.x) * (a.y - P.y);
    if (det < 0)
        return true;
    if (det > 0)
        return false;
}
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
#ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
#endif // HOME
    cin>>n;
    for (i=1; i<=n; i++)
    {
        cin>>v[i].x>>v[i].y;
    }
    sort (v+1,v+n+1,compare);
    st[++q]=1;
    st[++q]=2;
    viz[1]=viz[2]=1;
    for (i=3; i<=n; i++)
    {
        while (q>1&&determinant(v[st[q-1]],v[st[q]],v[i])<0)
        {
            viz[st[q]]=0;
            q--;
        }
        viz[i]=1;
        st[++q]=i;
    }
    for (i=n; i>=1; i--)
    {
        if (viz[i]==0)
        {
            while (q>1&&determinant(v[st[q-1]],v[st[q]],v[i])<0)
            {
                viz[st[q]]=0;
                q--;
            }
            viz[i]=1;
            st[++q]=i;
        }
    }
    while (q>1&&determinant(v[st[q-1]],v[st[q]],v[1])<0)
    {
        q--;
    }
    for (i=1; i<=q; i++)
    {
        ok[st[i]]=1;
    }
    for (i=1; i<=n; i++)
    {
        if (ok[i]==0)
        {
            primul= i ;
            break;
        }
    }
    ok[primul]=1;
    for (i=1; i<q; i++)
    {
        triunghiuri.push_back({st[i],st[i+1],primul});
    }
    triunghiuri.push_back({st[1],st[q],primul});
    for (i=1; i<=n; i++)
    {
        if (ok[i]==0)
        {
            ll loc=0;
            for (ll j=0; j<triunghiuri.size(); j++)
            {
                ll x=triunghiuri[j].a,y=triunghiuri[j].b,z=triunghiuri[j].c;
                ll val1 = ABS(determinant(v[x],v[y],v[i]));
                ll val2 = ABS(determinant(v[y],v[z],v[i]));
                ll val3 = ABS(determinant(v[z],v[x],v[i]));
                ll valfin = ABS(determinant(v[x],v[y],v[z]));
                if (val1+val2+val3==valfin)
                {
                    loc = j;
                    break;
                }
            }
            Triangle triunghi1= {triunghiuri[loc].a,triunghiuri[loc].b,i};
            Triangle triunghi2= {triunghiuri[loc].a,triunghiuri[loc].c,i};
            Triangle triunghi3= {triunghiuri[loc].b,triunghiuri[loc].c,i};
            triunghiuri.erase(triunghiuri.begin()+loc);
            triunghiuri.push_back(triunghi1);
            triunghiuri.push_back(triunghi2);
            triunghiuri.push_back(triunghi3);
        }
    }
    for (ll j=0; j<triunghiuri.size(); j++)
    {
        ll x=triunghiuri[j].a,y=triunghiuri[j].b,z=triunghiuri[j].c;
        Marc[x][y]=Marc[y][x]=Marc[x][z]=Marc[z][x]=Marc[z][y]=Marc[y][z]=1;
    }
    for (i=1; i<=n; i++)
    {
        for (j=i+1; j<=n; j++)
        {
            if (Marc[i][j])
            {
                candidati.push_back({i,j});
            }
        }
    }
    ll sum=0;
    for (i=0; i<candidati.size(); i++)
    {
        vector <int> neg,poz;
        int ok1=1;
        P = v[candidati[i].first];
        Punct Q = v[candidati[i].second];
        if (P.y<Q.y||(P.y==Q.y&&P.x>Q.x))
        {
            swap(P,Q);
        }
        for (j=1; j<=n; j++)
        {
            if (j==candidati[i].first||j==candidati[i].second)
            {
                continue;
            }
            if (determinant(P,Q,v[j])<0)
            {
                neg.push_back(j);
            }
            else
            {
                poz.push_back(j);
            }
        }
        sort (neg.begin(),neg.end(),compare2);
        sort (poz.begin(),poz.end(),compare2);
        int st=-1;
        for (j=0; j<poz.size(); j++)
        {
            for (int k=0; k<neg.size(); k++)
            {
                if (determinant(v[poz[j]],Q,v[neg[k]])<0&&determinant(v[poz[j]],P,v[neg[k]])>0)
                {
                    ok1=0;
                    break;
                }
            }
            /*while (st+1<(int)neg.size()&&determinant(v[poz[j]],P,v[neg[st+1]])>0)
            {
                st++;
            }
            if (st==-1)
            {
                continue;
            }
            if (determinant(v[poz[j]],Q,v[neg[st]])<0)
            {
                ok1=0;
                break;
            }*/
        }
        sum=sum+ok1;
    }
    cout<<sum;
    return 0;
}

Compilation message (stderr)

geometrija.cpp: In function 'int main()':
geometrija.cpp:156:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Triangle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |             for (ll j=0; j<triunghiuri.size(); j++)
      |                          ~^~~~~~~~~~~~~~~~~~~
geometrija.cpp:178:19: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<Triangle>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for (ll j=0; j<triunghiuri.size(); j++)
      |                  ~^~~~~~~~~~~~~~~~~~~
geometrija.cpp:194:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |     for (i=0; i<candidati.size(); i++)
      |               ~^~~~~~~~~~~~~~~~~
geometrija.cpp:222:20: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  222 |         for (j=0; j<poz.size(); j++)
      |                   ~^~~~~~~~~~~
geometrija.cpp:224:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  224 |             for (int k=0; k<neg.size(); k++)
      |                           ~^~~~~~~~~~~
geometrija.cpp:221:13: warning: unused variable 'st' [-Wunused-variable]
  221 |         int st=-1;
      |             ^~
geometrija.cpp: In function 'bool compare2(int, int)':
geometrija.cpp:88:1: warning: control reaches end of non-void function [-Wreturn-type]
   88 | }
      | ^

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 60 / 60