Submission #892056

#	Time	Username	Problem	Language	Result	Execution time	Memory
892056		urosk	Fence (CEOI08_fence)	C++14	90 / 100	8 ms	504 KiB

fence

#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define eb emplace_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}
#define si(a) (ll)(a.size())
using namespace std;

#define maxn 205
ll n,m;
pll a[maxn];
pll b[maxn];
ll dis[maxn];
ll cross(pll a,pll b,pll c){
    return (b.fi-a.fi)*(c.sc-a.sc) - (b.sc-a.sc)*(c.fi-a.fi);
}
vector<ll> g[maxn];
void tc(){
    cin >> n >> m;
    for(ll i = 1;i<=n;i++) cin >> a[i].fi >> a[i].sc;
    for(ll i = 1;i<=m;i++) cin >> b[i].fi >> b[i].sc;
    sort(a+1,a+1+n);
    vector<pll> hull;
    for(ll ii = 0;ii<2;ii++){
        ll siz = si(hull);
        for(ll i = 1;i<=n;i++){
            while(si(hull)>=2+siz){
                pll x = hull[si(hull)-2];
                pll y = hull[si(hull)-1];
                if(cross(x,y,a[i])<=0) break;
                hull.popb();
            }
            hull.pb(a[i]);
        }
        hull.popb();
        reverse(a+1,a+n+1);
    }
    //dbg(si(hull));
    hull.pb(hull[0]);
    ll ans = 0;
    vector<pll> v;

    for(ll i = 1;i<=m;i++){
        set<bool> s;
        for(ll j = 0;j+1<si(hull);j++){
            bool f = cross(hull[j],hull[j+1],b[i])>0;
            s.insert(f);
        }
        if(si(s)==1) v.pb(b[i]);
    }
    if(si(v)==0){cout<<n*20<<endl;return;}
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=n;j++){
            if(i==j) continue;
            set<bool> s;
            for(pll p : v){
                s.insert(cross(a[i],a[j],p)>0);
                //cerr<<i<< " "<<j<< " "<<p.fi<< " "<<p.sc<< " "<<cross(a[i],a[j],p)<<endl;

            }
            if((si(s)==1)&&((*s.begin())==0)){
                g[i].pb(j);
                //cerr<<"ij: "<<i<< " "<<j<<" "<<*s.begin()<<endl;
            }
        }
    }
    //dbg(si(v));
    ll minlen = llinf;
    for(ll i = 1;i<=n;i++){
        for(ll i = 1;i<=n;i++) dis[i] = llinf;
        queue<ll> q;
        q.push(i);
        dis[i] = 0;
        //dbg(minlen);
        while(si(q)){
            ll u = q.front();
            q.pop();
            for(ll s : g[u]){
                if(dis[s]==llinf){
                    dis[s] = dis[u] + 1;
                    q.push(s);
                }else if(s==i) minlen = min(minlen,dis[u]+1);
            }
        }
    }
    //dbg(minlen);
    cout<<(m-si(v))*111+minlen*20;
}

int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	int t; t = 1;
	while(t--){
		tc();
	}
	return (0-0);
}
/**
4 0
800 300
200 200
200 700
600 700
**/

Compilation message (stderr)

fence.cpp: In function 'void tc()':
fence.cpp:55:8: warning: unused variable 'ans' [-Wunused-variable]
   55 |     ll ans = 0;
      |        ^~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10