#include <bits/stdc++.h>
#define ll long long
#define MAXN 110
using namespace std;
struct point
{
ll x,y;
};
ll n,m,dist[MAXN];
point h[MAXN],t[MAXN],p0;
bool in[MAXN];
ll Cross(point c,point a,point b)
{
return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);
}
bool Cmp(point a,point b)
{
return Cross(p0,a,b)>0;
}
vector<point> ch;
void Convex_Hull()
{
ll ind=1;
for (ll i=2;i<=n;i++)
{
if (h[i].y<h[ind].y || (h[i].y==h[ind].y && h[i].x<h[ind].x))
ind=i;
}
swap(h[1],h[ind]);
p0=h[1];
sort(h+2,h+1+n,Cmp);
stack<point> s;
s.push(h[1]);
s.push(h[2]);
s.push(h[3]);
for (ll i=4;i<=n;i++)
{
point a=s.top(),b;
s.pop();
b=s.top();
s.push(a);
while (Cross(b,a,h[i])<0)
{
s.pop();
a=s.top();
s.pop();
b=s.top();
s.push(a);
}
s.push(h[i]);
}
while (!s.empty())
{
ch.push_back(s.top());
s.pop();
}
reverse(ch.begin(),ch.end());
}
vector<ll> G[MAXN];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m;
for (ll i=1;i<=n;i++)
cin >> h[i].x >> h[i].y;
for (ll i=1;i<=m;i++)
cin >> t[i].x >> t[i].y;
Convex_Hull();
ll ans=111*m,cnt=0;
if (ch.size()<3)
{
cout << ans;
return 0;
}
for (ll i=1;i<=m;i++)
{
in[i]=true;
for (ll j=0;j<ch.size();j++)
{
point a=ch[j],b=t[i],c=(!j)?ch[ch.size()-1] : ch[j-1];
in[i]=(in[i] && Cross(c,a,b)>0);
}
cnt+=in[i];
}
for (ll i=1;i<=n;i++)
{
for (ll j=1;j<=n;j++)
{
if (i==j)
continue;
bool yes=true;
for (ll l=1;l<=m;l++)
{
if (in[l] && Cross(h[i],h[j],t[l])<0)
{
yes=false;
break;
}
}
if (yes)
G[i].push_back(j);
}
}
for (ll i=1;i<=n;i++)
{
for (ll j=1;j<=n;j++)
dist[j]=LLONG_MAX;
dist[i]=1;
ll minn=LLONG_MAX;
queue<ll> q;
q.push(i);
while (!q.empty())
{
ll t=q.front();
q.pop();
for (ll next : G[t])
{
if (next==i)
minn=min(minn,dist[t]);
if (dist[t]+1<dist[next])
{
dist[next]=dist[t]+1;
q.push(next);
}
}
}
if (minn!=LLONG_MAX)
ans=min(ans,(m-cnt)*111+minn*20);
}
cout << ans;
return 0;
}
Compilation message
fence.cpp: In function 'int main()':
fence.cpp:78:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for (ll j=0;j<ch.size();j++)
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
468 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
