[白俊]2554刑務所建設


白駿2254刑務所建設

  • https://www.acmicpc.net/problem/2254

  • 内部が最大で何層牛の座標の凸の殻の問題を含むことができることを求めます
  • #include <iostream>
    #include <vector>
    #include <utility>
    #include <algorithm>
    using namespace std;
    
    typedef long long ll;
    typedef pair<ll, ll> dot;
    typedef vector<dot> polygon;
    
    vector<dot> dots;
    
    int ccw(dot a, dot b) {
    	ll cross = a.first * b.second - a.second * b.first;
    
    	if (cross > 0) return 1;
    	else if (cross < 0) return -1;
    	else return 0;
    }
    
    int ccw(dot p, dot a, dot b) {
    	a.first -= p.first; a.second -= p.second;
    	b.first -= p.first; b.second -= p.second;
    	return ccw(a, b);
    }
    
    bool leftTurn(dot p, dot a, dot b) {
    	return ccw(p, a, b) > 0;
    }
    
    bool cmp(dot& a, dot& b) {
    	dot a0 = make_pair(a.first - dots[0].first, a.second - dots[0].second);
    	dot b0 = make_pair(b.first - dots[0].first, b.second - dots[0].second);
    
    	ll cross = a0.first * b0.second - a0.second * b0.first;
    
    	if (cross != 0)
    		return (cross > 0);
    
    	if (a0.second != b0.second)
    		return a0.second < b0.second ;
    	return a0.first < b0.first;
    }
    
    void quickSortByAngle(int first, int last) {
    	if (first >= last) return;
    
    	int pivot = first;
    	int i = first + 1;
    	int j = last;
    
    	while (i <= j) {
    		while (cmp(dots[i], dots[pivot]) && i <= last) i++;
    		while (!cmp(dots[j], dots[pivot]) && j > first) j--;
    
    		if (i >= j) break;
    
    		swap(dots[i], dots[j]);
    	}
    	swap(dots[pivot], dots[j]);
    
    	quickSortByAngle(first, j - 1);
    	quickSortByAngle(j + 1, last);
    	return;
    }
    
    polygon convexHull() {
    	int minX = 1000000000, minY = 1000000000, minIdx = 0;
    	for (int i = 0; i < dots.size(); i++) {
    		if (minY > dots[i].second || (minY == dots[i].second && minX > dots[i].first)) {
    			minX = dots[i].first;
    			minY = dots[i].second;
    			minIdx = i;
    		}
    	}
    	swap(dots[minIdx], dots[0]);
    
    	quickSortByAngle(1, dots.size() - 1);
    
    	vector<int> stack(dots.size());
    	int idx = -1;
    	stack[++idx] = 0;
    	stack[++idx] = 1;
    
    	int next = 2;
    	while (next < dots.size()) {
    		while ((idx + 1) >= 2) {
    			int second = stack[idx--];
    			int first = stack[idx];
    
    			if (leftTurn(dots[first], dots[second], dots[next])) {
    				stack[++idx] = second;
    				break;
    			}
    		}
    		stack[++idx] = next++;
    	}
    
    	//볼록 껍질 반환
    	polygon hull;
    	for (int i = 0; i < idx + 1; ++i)
    		hull.push_back(dots[stack[i]]);
    	
    	return hull;
    }
    
    bool isInside(dot q, const polygon& p) {
    	int crosses = 0;
    	for (int i = 0; i < p.size(); ++i) {
    		int j = (i + 1) % p.size();
    		if (p[i].second > q.second != p[j].second > q.second) {
    			double atX = (p[j].first - p[i].first)*(q.second - p[i].second) / (p[j].second - p[i].second) + p[i].first;
    			if (q.first < atX) {
    				++crosses;
    			}
    		}
    	}
    	return crosses % 2 > 0;
    }
    
    
    int main(void) {
    	cin.tie(NULL);
    	ios::sync_with_stdio(false);
    
    	int N;
    	cin >> N;
    
    	dot cow;
    	cin >> cow.first >> cow.second;
    
    	for (int i = 0; i < N; i++) {
    		ll x, y;
    		cin >> x >> y;
    		dots.push_back(make_pair(x, y));
    	}
    	
    	int cnt = 0;
    	while (true) {
    		//더이상 볼록 껍질을 만들 수 없으면 종료
    		if (dots.size() < 3) break;
    
    		polygon hull = convexHull();
    		//볼록 껍질 내부에 소가 있는지 확인
    		if (isInside(cow, hull)) {
    			++cnt;
    			//dots에서 hull에 포함된 점 제거
    			for (int i = 0; i < hull.size(); ++i)
    				dots.erase(find(dots.begin(), dots.end(), hull[i]));
    		}
    		else break;
    	}
    
    	cout << cnt;
    	return 0;
    }