Submission #388363

#	Time	Username	Problem	Language	Result	Execution time	Memory
388363		abra_stone	공룡 발자국 (KOI18_footprint)	C++14	100 / 100	1728 ms	185668 KiB

footprint

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#define N 3005
using namespace std;

typedef long long ll;
struct st{
	ll x, y, id;
} o, a[N];
ll n, ans, d1[N][N], d2[N][N], h1[N][N], h2[N][N];
vector<st> lt, rt;

ll ccw(st p, st q, st r) {
	return p.x * q.y + q.x * r.y + r.x * p.y - q.x * p.y - r.x * q.y - p.x * r.y;
}

bool cmp(st p, st q) {return ccw(o, p, q) > 0;}

bool cmpmn(st p, st q) {
	if (p.y != q.y) return p.y < q.y;
	else return p.x < q.x;
}

void print(ll p, ll q, ll r) {
	if (p == 0) {printf("%lld %lld\n", a[p].x, a[p].y); return;}
	if (r == 1) print(q, h1[p][q], 2);
	else print(q, h2[p][q], 1);
	printf("%lld %lld\n", a[p].x, a[p].y);
}

int main()
{
	ll i, j, k;
	cin >> n;
	for (i = 0; i < n; i++) {
		scanf("%lld %lld", &a[i].x, &a[i].y);
	}
	sort(a, a + n, cmpmn);
	o = a[0];
	sort(a + 1, a + n, cmp);
	for (i = 0; i < n; i++) a[i].id = i;

	for (i = 1; i < n; i++) d1[i][0] = 2;
	for (i = 1; i < n; i++) {
		lt.clear(); rt.clear();
		rt.push_back(a[0]);
		for (j = 1; j < i; j++) if (ccw(a[0], a[i], a[j])) rt.push_back(a[j]);
		for (j = i + 1; j < n; j++) if (ccw(a[0], a[i], a[j])) lt.push_back(a[j]);
		o = a[i];
		sort(lt.begin(), lt.end(), cmp);
		sort(rt.begin(), rt.end(), cmp);

		ll mx = -1e9, mi = 0;
		ll I = a[i].id;
		for (j = 0, k = 0; j < lt.size(); j++) {
			ll J = lt[j].id;
			for (; k < rt.size(); k++) {
				ll K = rt[k].id;
				if (ccw(rt[k], a[i], lt[j]) <= 0) break;
				if (d1[I][K] + 1 > mx) mx = d1[I][K] + 1, mi = K;
			}
			d2[J][I] = mx;
			h2[J][I] = mi;
		}
		mx = -1e9, mi = 0;
		for (j = (ll)lt.size() - 1, k = (ll)rt.size() - 1; j >= 0; j--) {
			ll J = lt[j].id;
			for (; k >= 0; k--) {
				ll K = rt[k].id;
				if (ccw(rt[k], a[i], lt[j]) >= 0) break;
				if (d2[I][K] + 1 > mx) mx = d2[I][K] + 1, mi = K;
			}
			d1[J][I] = mx;
			h1[J][I] = mi;
		}
	}
	for (i = 0; i < n; i++) for (j = 0; j < i; j++) ans = max(ans, d1[i][j]);
	if (ans <= 3) {cout << '0'; return 0;}
    cout << ans << endl;
    for (i = 0; i < n; i++) for (j = 0; j < i; j++) if (d1[i][j] == ans) {print(i, j, 1); return 0;}
    return 0;
}

Compilation message (stderr)

footprint.cpp: In function 'int main()':
footprint.cpp:57:24: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |   for (j = 0, k = 0; j < lt.size(); j++) {
      |                      ~~^~~~~~~~~~~
footprint.cpp:59:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<st>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |    for (; k < rt.size(); k++) {
      |           ~~^~~~~~~~~~~
footprint.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   38 |   scanf("%lld %lld", &a[i].x, &a[i].y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 12 / 12
• Subtask 3: 29 / 29
• Subtask 4: 45 / 45