列表

详情

NC24027. [USACO 2016 Jan G]Lights Out

描述

Farmer John has installed a fancy new milking machine in his barn, but it draws so much power that it occasionally causes the power to go out! This happens so often that Bessie has memorized a map of the barn, making it easier for her to find the exit of the barn in the dark. She is curious though about the impact of power loss on her ability to exit the barn quickly. For example, she wonders how much farther she might need to walk find the exit in the dark.
The barn is described by a simple (non self-intersecting) polygon with integer vertices (x1,y1)…(xn,yn) listed in clockwise order. Its edges alternate between horizontal (parallel to the x-axis) and vertical (parallel to the y-axis); the first edge can be of either type. The exit is located at (x1,y1). Bessie starts inside the barn located at some vertex (xi,yi) for i>1. She can walk only around the perimeter of the barn, either clockwise or counterclockwise, Her goal is to travel a minimum distance to reach the exit. This is relatively easy to do with the lights on, of course, since she will travel either clockwise or counterclockwise from her current location to the exit -- whichever direction is shorter.

One day, the lights go out, causing Bessie to panic and forget which vertex she is standing at. Fortunately, she still remembers the exact map of the barn, so she can possibly figure out her position by walking around and using her sense of touch. Whenever she is standing at a vertex (including at her initial vertex), she can feel the exact interior angle at that vertex, and she can tell if that vertex is the exit. When she walks along an edge of the barn, she can determine the exact length of the edge after walking along the entire edge. Bessie decides on the following strategy: she will move clockwise around the perimeter of the barn until she has felt enough angles and edges to deduce the vertex at which she is currently located. At that point, she can easily figure out how to get to the exit by traveling a minimum amount of remaining distance, either by continuing to move clockwise or by switching direction and moving counter-clockwise.

Please help Bessie determine the largest amount by which her travel distance will increase in the worst case (over all possibilities for her starting vertex) for travel in the dark versus in a lit barn.

输入描述

The first line of the input contains N (4≤N≤200). Each of the next N lines contains two integers, describing the points (xi,yi) in clockwise order around the barn. These integers are in the range −100,000…100,000.

输出描述

Output the largest amount that Bessie's travel distance will increase in the worst case starting position using the strategy in the problem statement.

示例1

输入: 

4
0 0
0 10
1 10
1 0

输出: 

2

说明:

In this example, Bessie can feel that she is initially standing at a 90-degree angle, but she cannot tell if she is initially standing at vertex 2, 3, or 4. After taking a step along one edge in the clockwise direction, Bessie either reaches the exit or can uniquely determine her location based on the length of this edge. The distances she obtains are:

If starting at vertex 2: she travels 12 units in the dark (1 unit to reach vertex 3, then 11 units to continue to the exit). She only needs to travel 10 units in a lit barn. This is an extra distance of 2 for this vertex.

If starting at vertex 3: she travels 11 units in both cases.

If starting at vertex 4: she travels 1 unit in both cases.

The worst-case difference over all starting points is therefore 12 - 10 = 2. That is, Bessie can guarantee that using her strategy, no matter where she starts, she will travel at most 2 extra units of distance farther in the dark than in the light.

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

Python3(3.9) 解法, 执行用时: 54ms, 内存消耗: 3052K, 提交时间: 2020-12-20 23:49:30 

N = int(input())
vertices = []
dists = []
prev = None
for _ in range(N):
    s, t = tuple(map(int, input().split()))
    if vertices:
        dists.append(abs(vertices[-1][0] - s) + abs(vertices[-1][1] - t))
    vertices.append((s, t))
# dist between last vertex and first
dists.append(abs(vertices[0][0] - vertices[-1][0]) + \
             abs(vertices[0][1] - vertices[-1][1]))

angles = []  # records the angle at the vertex
for i in range(N):
    prev, cur, nxt = vertices[i - 1], vertices[i], vertices[(i + 1) % N]
    if prev[1] == cur[1] and prev[0] > cur[0] and cur[0] == nxt[0] and cur[1] < nxt[1]:
        angles.append(90)
    elif prev[0] == cur[0] and prev[1] < cur[1] and cur[1] == nxt[1] and cur[0] < nxt[0]:
        angles.append(90)
    elif prev[1] == cur[1] and prev[0] < cur[0] and cur[0] == nxt[0] and cur[1] > nxt[1]:
        angles.append(90)
    elif prev[0] == cur[0] and prev[1] > cur[1] and cur[1] == nxt[1] and cur[0] > nxt[0]:
        angles.append(90)
    else:
        angles.append(270)

# find other starting angles with same value
def find_others(start_index):
    res = []
    a = angles[start_index]
    for i in range(1, N):
        if (i + start_index != N) and angles[(i + start_index) % N] == a:
            res.append((i + start_index) % N)
    return res


# find the result corresponding to a start_index
def simulate(start_index):
    optimal_dist = min(sum(dists[start_index:]), sum(dists[:start_index]))
    indices = find_others((start_index))  # feel the first angle
    total_dist = 0
    inc = 0
    while indices:
        total_dist += dists[start_index + inc]
        inc += 1
        if start_index + inc == N:
            return total_dist - optimal_dist
        indices = [i for i in indices if i + inc != N and dists[(i + inc - 1) % N] == dists[(start_index + inc - 1) % N] \
                   and angles[(i + inc) % N] == angles[(start_index + inc) % N]]

    total_dist += min(sum(dists[(start_index + inc) % N:]), sum(dists[:(start_index + inc) % N]))
    return total_dist - optimal_dist


res = 0
for i in range(1, N):
    res = max(res, simulate(i))
print(res)

C++(clang++11) 解法, 执行用时: 38ms, 内存消耗: 12328K, 提交时间: 2020-12-19 21:17:48 

#include <bits/stdc++.h>
#define rgi  int
#define ll long long

using namespace std;
inline int read() {
	int f=1,x=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct node{
	int x,y;
}p[205];
int n,f[205];
void Cir(int &x){
	if(x==n+1) x=1;
	if(x==n+2) x=2;
	if(x==0) x=n;
}
inline int CrossProduct(int x1,int y1,int x2,int y2){
	return x1*y2-x2*y1; 
}
inline int dist(int i,int j){
	return abs(p[i].x-p[j].x)+abs(p[i].y-p[j].y);
}
int main() {

	ios::sync_with_stdio(0);cin.tie(0);
	vector<int> S;
	S.push_back(0);
	n=read();
	for(rgi i=1;i<=n;++i){
		p[i].x=read();
		p[i].y=read();
	}
	for(rgi i=1;i<=n;++i){
		int j=i+1,k=i+2;
		Cir(j); Cir(k);
		S.push_back(dist(i,j));

		if(CrossProduct(p[j].x-p[i].x,p[j].y-p[i].y,p[k].x-p[j].x,p[k].y-p[j].y)>0)
			S.push_back(-1);
		else S.push_back(-2);
	}
	S.back()=0;
	for(rgi i=2;i<=n;++i){
		int j=i+1; Cir(j);
		int tmp1=dist(i,j);
		while(j!=1){
			int jj=j;
			j++; Cir(j);
			tmp1+=dist(jj,j);
		}
		j=i-1; Cir(j);
		int tmp2=dist(i,j);
		while(j!=1){
			int jj=j;
			j--; Cir(j);
			tmp2+=dist(jj,j);
		}
		f[i]=min(tmp1,tmp2);
	}
	multiset<vector<int> > Set;
	for(rgi i=0;i<(int)S.size();i+=2){
		for(rgi j=1;i+j<=(int)S.size();j+=2){
			Set.insert(vector<int>(S.begin()+i,S.begin()+i+j));
		}
	}
	int ans=0;
	for(rgi i=2;i<=n;++i){
		int j,cost=0;
		for(j=1;;j+=2){
			if(Set.count(vector<int>(S.begin()+(i-1)*2,S.begin()+(i-1)*2+j))==1)
				break;
			cost+=S[(i-1)*2+j];
		}
		ans=max(ans,cost+f[i+j/2]-f[i]);
	}
	cout<<ans<<endl;
	return 0;
}

上一题

© 2024 nowcoder.com