Submission #119225

#TimeUsernameProblemLanguageResultExecution timeMemory
119225davitmargTriangles (CEOI18_tri)C++17
0 / 100
3 ms512 KiB
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>

#ifndef death
    #include<trilib.h>
#endif // death

#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

#ifdef death

int get_n()
{
    cout<<"N::"<<endl;
    int x;
    cin>>x;
    return x;
}

bool is_clockwise(int a, int b, int c)
{
    cout<<":::"<<a<<" "<<b<<" "<<c<<endl;
    int x;
    cin>>x;
    return x;
}

void give_answer(int x)
{
    cout<<x<<endl;
}

#endif // death

map<pair<int,pair<int,int>>,bool> used,pre;

bool cw(int a,int b,int c)
{
    if(used[MP(a,MP(b,c))])
        return pre[MP(a,MP(b,c))];
    used[MP(a,MP(b,c))]=1;
     return pre[MP(a,MP(b,c))]=is_clockwise(a,b,c);
}

bool ccw(int a,int b,int c)
{
    return !cw(a,b,c);
}

int convex(vector<int>& p)
{
    vector<int> up,down;
    int st,en;

    reverse(all(p));
    p.pop_back();
    reverse(all(p));
    p.pop_back();
    vector<int> add=p;
    p.clear();
    p.PB(st);
    for(int i=0;i<add.size();i++)
        for(int j=0;j<add.size();j++)
            p.PB(add[j]);
    p.PB(en);

    st=p[0];
    en=p.back();

    up.PB(p[0]);
    down.PB(p[0]);
    for(int i=1;i<p.size();i++)
    {
        if(i==p.size()-1 || cw(p[0],p[i],p[p.size()-1]))
        {
            while(up.size()>1 && !cw(up[up.size()-2],up[up.size()-1],p[i]) )
                up.pop_back();
            up.PB(p[i]);
        }

        if(i==p.size()-1 || ccw(p[0],p[i],p[p.size()-1]))
        {
            while(down.size()>1 && !cw(down[down.size()-2],down[down.size()-1],p[i]) )
                down.pop_back();
            down.PB(p[i]);
        }
    }
    down.pop_back();
    reverse(all(down));
    down.pop_back();
    for(int i=0;i<down.size();i++)
        up.PB(down[i]);
    return up.size();
}

int ans,n;
vector<int> p;
int main()
{
    n=get_n();
    for(int i=1;i<=n;i++)
        p.PB(i);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==j)
                continue;
            swap(p[1],p[i]);
            swap(p[n],p[j]);
            ans=max(ans,convex(p));
            swap(p[1],p[i]);
            swap(p[n],p[j]);
        }
    give_answer(ans);
	return 0;
}


/*


*/

Compilation message (stderr)

tri.cpp: In function 'int convex(std::vector<int>&)':
tri.cpp:82:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<add.size();i++)
                 ~^~~~~~~~~~~
tri.cpp:83:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<add.size();j++)
                     ~^~~~~~~~~~~
tri.cpp:92:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<p.size();i++)
                 ~^~~~~~~~~
tri.cpp:94:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i==p.size()-1 || cw(p[0],p[i],p[p.size()-1]))
            ~^~~~~~~~~~~~
tri.cpp:101:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(i==p.size()-1 || ccw(p[0],p[i],p[p.size()-1]))
            ~^~~~~~~~~~~~
tri.cpp:111:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<down.size();i++)
                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...