15974번 - 공룡 발자국

C++14

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;
typedef pair<double, double> pd;

istream& operator >> (istream &in, p &v){
	in >> v.x >> v.y;
	return in;
}

ostream& operator << (ostream &out, const p &v){
	out << v.x << " " << v.y;
	return out;
}

int ccw(p a, p b, p c){
	ll res = (b.x-a.x)*(c.y-a.y);
	res -= (b.y-a.y)*(c.x-a.x);
	if(res > 0) return 1;
	if(res) return -1;
	return 0;
}

int ccw(pd a, pd b, pd c){
	double res = (b.x-a.x)*(c.y-a.y);
	res -= (b.y-a.y)*(c.x-a.x);
	if(res > 0) return 1;
	if(res) return -1;
	return 0;
}

bool chk(p a, p b, p c, p d){
	int ab = ccw(a, b, c) * ccw(a, b, d);
	int cd = ccw(c, d, a) * ccw(c, d, b);
	if(!ab && !cd){
		if(a > b) swap(a, b);
		if(c > d) swap(c, d);
		return !(b < c || d < a);
	}
	return ab <= 0 && cd <= 0;
}

bool chk(p _a, p _b, pd c, p _d){
	pd a = _a, b = _b, d = _d;
	int ab = ccw(a, b, c) * ccw(a, b, d);
	int cd = ccw(c, d, a) * ccw(c, d, b);
	if(!ab && !cd){
		if(a > b) swap(a, b);
		if(c > d) swap(c, d);
		return !(b < c || d < a);
	}
	return ab <= 0 && cd <= 0;
}

int n;
vector<p> v;
vector<p> now;
bool flag;

void sub1(){
	cout << n << "\n";
	for(auto i : v) cout << i << "\n";
}

int chk(){
	int n = now.size();
	if(n & 1) return 0;
	vector<p> &v = now;
	vector<p> u; //발가락
	for(int i=0; i<n-1; i++){
		int j = i + 1, k = i + 2;
		if(k == n) k = 0;
		if(j & 1) u.push_back(v[j]);
		if(j & 1){
			if(ccw(v[i], v[j], v[k]) != 1) return 0;
		}else{
			if(ccw(v[i], v[j], v[k]) != -1) return 0;
		}
	}
	for(int i=0; i<n; i++){
		int j = i + 1;
		if(j == n) j = 0;
		for(int k=0; k<u.size(); k++){
			if(i == 0 && k == 0) continue;
			if(j == 0 && k == u.size() - 1) continue;
			if(v[i] == u[k] || v[j] == u[k]) continue;
			double dx = u[k].x - v[0].x;
			double dy = u[k].y - v[0].y;
			dx /= dy; dx *= 0.000001;
			if(chk(v[i], v[j], make_pair<double>(v[0].x + dx, v[0].y+0.000001), u[k])){
				//if(flag) cout << "(" << v[i] << "), (" << v[j] << ") -> (" << u[k] << ")";
				return 0;
			}
		}
	}
	return n;
}

int main(){
	//subtask 2
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n; v.resize(n);
	for(auto &i : v) cin >> i;
	int idx = 0;
	for(int i=1; i<n; i++){
		if(v[i].y < v[idx].y) idx = i;
	}
	swap(v[0], v[idx]);
	sort(v.begin()+1, v.end(), [&](p &a, p &b){
		return ccw(v[0], a, b) > 0;
	});
	if(n > 10){
		sub1(); return 0;
	}

	
	int lim = 1 << n, ans = 0, mxbit = 0;
	for(int bit=0; bit<lim; bit++){
		now.clear();
		now.push_back(v[0]);
		for(int i=1; i<n; i++){
			if(bit & (1 << i)) now.push_back(v[i]);
		}
		if(bit == lim-1)  flag = 1;
		else flag = 0;
		int t = chk();
		if(ans < t){
			ans = t;
			mxbit = bit;
		}
	}
	cout << ans << "\n";
	if(ans){
		cout << v[0] << "\n";
		for(int i=1; i<n; i++){
			if(mxbit & (1 << i)) cout << v[i] << "\n";
		}
	}
}
결과	메모리	시간	코드 길이
26점	2152	0	2843
문제

문제

출처

ICPC

C++14

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
