oj.uz

Submission #893283

# Submission time Handle Problem Language Result Execution time Memory
893283 2023-12-26T20:39:19 Z Vovamatrix Fence (CEOI08_fence) C++14
50 / 100
 1 ms 600 KB 
//https://oj.uz/problem/view/CEOI08_fence
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define INF 1e15
#define MOD 1000000007
#define endl "\n"
 
#define all(data)       data.begin(),data.end()
#define TYPEMAX(type)   std::numeric_limits<type>::max()
#define TYPEMIN(type)   std::numeric_limits<type>::min()
#define MAXN 107
struct pt
{
    ll x,y;
    pt(){}
    pt(int u,int v) {x=u,y=v;}
};
pt operator + (pt a,pt b) {return pt(a.x+b.x,a.y+b.y);}
pt operator - (pt a,pt b) {return pt(a.x-b.x,a.y-b.y);}
ll cross(pt a,pt b) {return a.x*b.y-a.y*b.x;}
bool cw(pt a,pt b,pt c) {return cross(a-b,c-b)>=0;}
bool cmp1(pt a,pt b) {return mp(a.y,a.x)<mp(b.y,b.x);}
bool cmp2(pt a,pt b) {return cw(a,pt(0,0),b);}
vector<pt> ho,tr;
vector<ll> adj[MAXN];
bool vis[MAXN];
bool Inside(vector<pt> ch,pt a){
    bool check1=false,check2=false;
    for(int i=0;i<ch.size();i++)
    {
        if(cw(a,ch[i],ch[(i+1)%(ch.size())])) check1=true;
        else check2=true;
    }
    if(check1 && check2) return false;
    return true;
}
vector<pt> Convex_Hull(vector<pt> a)
{
    sort(all(a),cmp1); pt o=a[0];
    for(int i=0;i<a.size();i++) a[i]=a[i]-o;
    sort(a.begin()+1,a.end(),cmp2);
    vector<pt> ch;
    for(int i=0;i<a.size();i++)
    {
        while(ch.size()>=2 && cw(ch[ch.size()-2],ch.back(),a[i])) ch.pop_back();
        ch.pb(a[i]);
    }
    for(int i=0;i<ch.size();i++) ch[i]=ch[i]+o;
    return ch;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    ll n,m; cin>>n>>m; pt ptt;
    for(int i=1;i<=n;i++)
    {
        cin>>ptt.x>>ptt.y;
        ho.pb(ptt);
    }
    for(int i=1;i<=m;i++)
    {
        cin>>ptt.x>>ptt.y;
        tr.pb(ptt);
    }
    vector<pt> ch=Convex_Hull(ho);
    vector<pt> pts;
    for(auto p:tr)
    {
        if(Inside(ch,p)) pts.pb(p);
    }
    ll cnt=INF;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j) continue;
            bool check=true;
            for(auto p:pts)
            {
                if(!cw(p,ho[i],ho[j])) check=false;
            }
            if(check) adj[j].pb(i);
        }
    }
    for(int i=0;i<n;i++)
    {
        queue<pll> q; q.push({i,0}); ll mm=INF;
        for(int j=0;j<n;j++) vis[i]=false;
        bool cyc=false;
        while(!cyc && !q.empty())
        {
            ll j=q.front().fi,dd=q.front().sc;
            q.pop();
            for(auto k:adj[j])
            {
                if(k==i) {mm=dd+1; cyc=true; break;}
                if(!vis[k]) {q.push({k,dd+1}); vis[k]=true;}
            }
        }
        cnt=min(cnt,mm);
    }
    ll rez=min((ll)(111*(m-pts.size())+20*cnt),111*m);
    cout<<rez<<endl;
    return 0;
}

Compilation message

fence.cpp: In function 'bool Inside(std::vector<pt>, pt)':
fence.cpp:45:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     for(int i=0;i<ch.size();i++)
      |                 ~^~~~~~~~~~
fence.cpp: In function 'std::vector<pt> Convex_Hull(std::vector<pt>)':
fence.cpp:56:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(int i=0;i<a.size();i++) a[i]=a[i]-o;
      |                 ~^~~~~~~~~
fence.cpp:59:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0;i<a.size();i++)
      |                 ~^~~~~~~~~
fence.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<pt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<ch.size();i++) ch[i]=ch[i]+o;
      |                 ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -