| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 892064 |
2023-12-24T18:13:08 Z |
urosk |
Fence (CEOI08_fence) |
C++14 |
|
8 ms |
476 KB |
#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<<111*m<<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);
}
}
}
if(minlen==llinf) minlen = 0;
//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
fence.cpp: In function 'void tc()':
fence.cpp:55:8: warning: unused variable 'ans' [-Wunused-variable]
55 | ll ans = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
476 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
344 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
