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;

int dp[2][3030][3030];
int prv[2][3030][3030];

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

void go(int i, int j){
	for(int k=i+1; k<n; k++){
		if(ccw(v[0], v[j], v[k]) == 0) continue;
		int cw = ccw(v[i], v[j], v[k]);
		if(cw < 0 && dp[1][i][j] && dp[0][j][k] < dp[1][i][j] + 1){
			dp[0][j][k] = dp[1][i][j] + 1; prv[0][j][k] = i;
		}
		if(cw > 0 && dp[0][i][j] && dp[1][j][k] < dp[0][i][j] + 1){
			dp[1][j][k] = dp[0][i][j] + 1; prv[1][j][k] = i;
		}
	}
}

int main(){
	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 > 300) sub1();
	
	for(int i=1; i<n; i++) dp[0][0][i] = 2;
	for(int i=0; i<n; i++){
		for(int j=i+1; j<n; j++){
			go(i, j);
		}
	}

	int mx = 0, x = 0, y = 0;
	for(int i=1; i<n; i++){
		for(int j=i+1; j<n; j++){
			if(ccw(v[0], v[i], v[j]) != 1) continue;
			if(mx < dp[0][i][j]){
				mx = dp[0][i][j]; x = i, y = j;
			}
		}
	}
	if(!mx){
		cout << 0; return 0;
	}
	vector<int> ans; ans.push_back(y); ans.push_back(x);
	while(ans.back() != 0){
		int t = ans.size();
		ans.push_back(prv[t&1][ans[t-1]][ans[t-2]]);
	}
	reverse(ans.begin(), ans.end());
	cout << ans.size() << "\n";
	for(auto i : ans) cout << v[i] << "\n";
}
결과	메모리	시간	코드 길이
55점	145604	44	2542
문제

문제

출처

ICPC

C++14

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말
