oj.uz

Submission #898023

# Submission time Handle Problem Language Result Execution time Memory
898023 2024-01-04T08:05:23 Z AlphaMale06 Fence (CEOI08_fence) C++14
100 / 100
 1 ms 348 KB 
#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 << min(20*ans+111*cntdel, 111*m) << '\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;
      |          ~^~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 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
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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
10.0 / 10.0

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

Subtask #8
10.0 / 10.0

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

Subtask #9
10.0 / 10.0

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

Subtask #10
10.0 / 10.0

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