Submission #242191

#	Time	Username	Problem	Language	Result	Execution time	Memory
242191		arnold518	공룡 발자국 (KOI18_footprint)	C++14	14 / 100	1008 ms	134136 KiB

footprint

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 3000;
const ll INF = 1e9;

struct Point { ll x, y; };
bool operator == (const Point &p, const Point &q) { return p.x==q.x && p.y==q.y; }
Point operator + (const Point &p, const Point &q) { return {p.x+q.x, p.y+q.y}; }
Point operator - (const Point &p, const Point &q) { return {p.x-q.x, p.y-q.y}; }

ll ccw(Point p, Point q) { return p.x*q.y-p.y*q.x; }
ll ccw(Point p, Point q1, Point q2) { return ccw(q1-p, q2-p); }

int N;
Point A[MAXN+10], P={INF, INF};

pii dp1[MAXN+10][MAXN+10], dp2[MAXN+10][MAXN+10];
pair<int, pii> ans;

int main()
{
	int i, j, k;

	scanf("%d", &N);
	for(i=1; i<=N; i++) scanf("%lld%lld", &A[i].x, &A[i].y);
	for(i=1; i<=N; i++) if(A[i].y<P.y) P=A[i];
	for(i=1; i<=N; i++) if(A[i]==P) break;
	for(; i<N; i++) swap(A[i], A[i+1]);

	N--;
	sort(A+1, A+N+1, [&](const Point &p, const Point &q) { return ccw(P, p, q)<0; });

	for(i=1; i<=N; i++)
	{
		vector<int> L, R;
		for(j=i+1; j<=N; j++) R.push_back(j), dp1[j][i+1]=dp2[j][i+1]={-987654321, 0};
		for(j=1; j<i; j++) L.push_back(j);

		sort(L.begin(), L.end(), [&](const int &p, const int &q) { return ccw(A[i]-A[p], A[i]-A[q])<0; });
		sort(R.begin(), R.end(), [&](const int &p, const int &q) { return ccw(A[p]-A[i], A[q]-A[i])<0; });

		pii now={2, i};
		for(j=0, k=0; j<R.size(); j++)
		{
			for(; k<L.size() && ccw(A[i]-A[L[k]], A[R[j]]-A[i])<=0; k++) now=max(now, {dp2[L[k]][i].first+1, L[k]});
			dp1[i][R[j]]=max(dp1[i][R[j]], now);
		}

		now={-987654321, 0};
		for(j=R.size()-1, k=L.size()-1; j>=0; j--)
		{
			for(; k>=0 && ccw(A[i]-A[L[k]], A[R[j]]-A[i])>=0; k--) now=max(now, {dp1[L[k]][i].first+1, L[k]});
			dp2[i][R[j]]=max(dp2[i][R[j]], now);
			ans=max(ans, {dp2[i][R[j]].first, {i, R[j]}});
		}
	}
	assert(ans.first>0);
	vector<Point> V;
	pii v=ans.second; int t=2;
	V.push_back(P);
	while(1)
	{
		V.push_back(A[v.second]);
		if(v.first==v.second) break;
		if(t==2)
		{
			v={dp2[v.first][v.second].second, v.first};
			t=1;
		}
		else
		{
			v={dp1[v.first][v.second].second, v.first};
			t=2;
		}
	}

	printf("%d\n", V.size());
	for(auto it : V) printf("%lld %lld\n", it.x, it.y);
}

Compilation message (stderr)

footprint.cpp: In function 'int main()':
footprint.cpp:48:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0, k=0; j<R.size(); j++)
                 ~^~~~~~~~~
footprint.cpp:50:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(; k<L.size() && ccw(A[i]-A[L[k]], A[R[j]]-A[i])<=0; k++) now=max(now, {dp2[L[k]][i].first+1, L[k]});
          ~^~~~~~~~~
footprint.cpp:82:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<Point>::size_type {aka long unsigned int}' [-Wformat=]
  printf("%d\n", V.size());
                 ~~~~~~~~^
footprint.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
footprint.cpp:30:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld%lld", &A[i].x, &A[i].y);
                      ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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