Submission #898019

#	Time	Username	Problem	Language	Result	Execution time	Memory
898019		AlphaMale06	Fence (CEOI08_fence)	C++14	90 / 100	1 ms	456 KiB

fence

#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 (stderr)

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 / 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