Submission #349198

#	Time	Username	Problem	Language	Result	Execution time	Memory
349198		arnold518	Fence (CEOI08_fence)	C++14	60 / 100	438 ms	492 KiB

fence

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

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

const int MAXN = 100;

struct Point
{
	int x, y;
};

Point operator + (Point p, Point q) { return {p.x+q.x, p.y+q.y}; }
Point operator - (Point p, 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; }

int N, M;
Point A[MAXN+10], B[MAXN+10];
int C[MAXN+10][MAXN+10];

int dp[MAXN+10], ans=0;

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y);
	for(int i=1; i<=M; i++) scanf("%d%d", &B[i].x, &B[i].y);

	for(int i=1; i<=N; i++)
	{
		vector<int> V;
		for(int j=1; j<=N; j++) if(i!=j) V.push_back(j);

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

		for(int j=1; j<=N; j++)
		{
			if(j==i) continue;
			for(int k=1; k<=N; k++)
			{
				if(k==i) continue;
				if(k==j) continue;
				C[j][k]=0;
				for(int p=1; p<=M; p++)
				{
					if(ccw(A[j]-A[i], B[p]-A[i])>0 && ccw(A[k]-A[j], B[p]-A[j])>0 && ccw(A[i]-A[k], B[p]-A[k])>0) C[j][k]++;
				}
			}
		}

		for(int j=0; j<V.size(); j++)
		{
			dp[j]=40;
			for(int k=0; k<j; k++)
			{
				dp[j]=min(dp[j], dp[k]+20-C[V[k]][V[j]]*111);
			}
			ans=min(ans, dp[j]);
		}
	}
	printf("%d\n", ans+M*111);
}

Compilation message (stderr)

fence.cpp: In function 'int main()':
fence.cpp:56:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int j=0; j<V.size(); j++)
      |                ~^~~~~~~~~
fence.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   27 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
fence.cpp:28:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   28 |  for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
fence.cpp:29:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |  for(int i=1; i<=M; i++) scanf("%d%d", &B[i].x, &B[i].y);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 10
• Subtask 5: 10 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10