#include <bits/stdc++.h>
/*
Oce nas,
koji si na nebesima,
da se sveti ime Tvoje,
da dodje carstvo Tvoje,
da bude volja Tvoja,
i na zemlji, kao i na nebu.
Hleb nas nasusni daj nam danas,
i oprosti nam dugove nase,
kao sto i mi oprastamo duznicima svojim,
i ne uvedi nas u iskusenje,
no izbavi nas od zloga.
Jer je Tvoje Carstvo,
i sila, i slava,
u vekove vekova.
Amin.
*/
using namespace std;
typedef vector<int> vc;
typedef vector<vector<int>> vvc;
using ll = long long;
using ld = long double;
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define F first
#define S second
#define pb push_back
#define pf push_front
#define all(x) (x).begin(), (x).end()
#define int long long
struct point{
int x, y, index;
};
bool cmp(point a, point b){
if(a.x==b.x)return a.y<b.y;
return a.x<b.x;
}
vector<point> c;
vector<point> g;
bool isLeft(point a, point b, point c){
return ((b.x-a.x)*(c.y-a.y)>(b.y-a.y)*(c.x-a.x));
}
bool InConvexHull(point p, vector<point> & upper, vector<point> & lower){
int szu=upper.size(), szl=lower.size();
if(p.x < upper[0].x || p.x > upper.back().x)return 0;
if(szu==2 && isLeft(upper[0], upper[1], p))return 0;
if(szl==2 && isLeft(lower[1], lower[0], p))return 0;
if(szu!=2){
int l=0; int r=szu-2;
while(l<=r){
int s=l+r>>1;
if(p.x>=upper[s].x && p.x <=upper[s+1].x){
if(isLeft(upper[s], upper[s+1], p))return 0;
break;
}
if(p.x<upper[s].x)r=s-1;
else l=s+1;
}
}
if(szl!=2){
int l=0; int r=szl-2;
while(l<=r){
int s=l+r>>1;
if(p.x>=lower[s].x && p.x <=lower[s+1].x){
if(!isLeft(lower[s], lower[s+1], p))return 0;
break;
}
if(p.x<lower[s].x)r=s-1;
else l=s+1;
}
}
return 1;
}
const int N = 101;
vector<int> adj[N];
bool mark[N];
int cyc;
int d[N];
bool isdel[N];
void bfs(int v){
queue<int> q;
q.push(v);
d[v]=0;
while(q.size()){
int nd=q.front();
for(int to : adj[nd]){
if(to==v){
cyc=d[nd]+1;
return;
}
if(!mark[to]){
mark[to]=1;
d[to]=d[nd]+1;
q.push(to);
}
}
q.pop();
}
}
void solve(){
int n, m;
cin >> n >> m;
for(int i=0; i< n; i++){
int x, y;
cin >> x >> y;
c.pb({x, y, i});
}
for(int i=0; i< m; i++){
int x, y;
cin >> x >> y;
g.pb({x, y, i});
}
sort(all(c), cmp);
point A = c[0];
point B = c.back();
vector<point> upperset;
vector<point> lowerset;
for(int i=1; i<(int)c.size()-1; i++){
if(isLeft(A, B, c[i]))upperset.pb(c[i]);
else lowerset.pb(c[i]);
}
upperset.pb(B); lowerset.pb(B);
vector<point> upperhull;
vector<point> lowerhull;
upperhull.pb(A); lowerhull.pb(A);
for(point p : upperset){
int sz=upperhull.size();
if(sz==1){
upperhull.pb(p);
continue;
}
while(sz>=2 && isLeft(upperhull[sz-2], upperhull[sz-1], p)){
upperhull.pop_back();
sz--;
}
upperhull.pb(p);
}
for(point p : lowerset){
int sz=lowerhull.size();
if(sz==1){
lowerhull.pb(p);
continue;
}
while(sz>=2 && !isLeft(lowerhull[sz-2], lowerhull[sz-1], p)){
lowerhull.pop_back();
sz--;
}
lowerhull.pb(p);
}
int cntdel=0;
for(point p : g){
if(!InConvexHull(p, upperhull, lowerhull)){
cntdel++;
isdel[p.index]=1;
}
}
for(point p : c){
for(point q : c){
if(p.x==q.x && p.y==q.y)continue;
bool ok=1;
for(point r : g){
if(isdel[r.index])continue;
if(!isLeft(p, q, r)){
ok=0;
break;
}
}
if(ok)adj[p.index].pb(q.index);
}
}
int ans=100;
for(point p : c){
cyc=-1;
for(int i=0; i<=100; i++){
mark[i]=0;
d[i]=1e9;
}
bfs(p.index);
if(cyc!=-1)ans=min(ans, cyc);
}
cout << 20*ans+111*cntdel << '\n';
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
solve();
}
Compilation message
fence.cpp: In function 'bool InConvexHull(point, std::vector<point>&, std::vector<point>&)':
fence.cpp:63:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
63 | int s=l+r>>1;
| ~^~
fence.cpp:75:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int s=l+r>>1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 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 |
0 ms |
344 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 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
456 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 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 |
