제출 #349199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
349199		arnold518	Fence (CEOI08_fence)	C++14	100 / 100	443 ms	512 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(A[i].y<A[j].y || (A[i].y==A[j].y && A[i].x<A[j].x)) 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);
}

컴파일 시 표준 에러 (stderr) 메시지

fence.cpp: In function 'int main()':
fence.cpp:59:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   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: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10