codeforces #346 div 2 D. Bicycle Race (思维，计算几何，公式)

题目链接题意：给出n+1个点，每次由i点到i+1点，每段线段之间保证不同向或者反向，第一个点和最后一个点保证重合。路径围城的封闭图形中间都是水，问有多少个危险点，使得如果在这个点忘记转弯就会掉进水里。

思路：搞了半天没搞出来qaq

From the track description follows that Maria moves the way that the water always located to the right from her, so she could fall into the water only while turning left. To check if the turn is to the left, let’s give every Maria’s moves directions a number: moving to the north — 0, moving to the west — 1, to the south — 2 and to the east — 3. Then the turn is to the left if and only if the number of direction after performing a turn dir is equal to the number before performing a turn oldDir plus one modulo 4
.
This solution has complexity O(n).

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年03月31日 星期四 01时51分56秒
 4File Name :code/cf/#346/D.cpp
 5************************************************ */
 6
 7#include <cstdio>
 8#include <cstring>
 9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1005;
34int n;
35int dir[N];
36
37struct node
38{
39    int x,y;
40    int getdir( node b)
41    {
42	if (x==b.x)
43	{
44	    if (y>b.y) return 0;
45	    else return 2;
46	}
47	else
48	{
49	    if (x>b.x) return 1;
50	    else return 3;
51	}
52    }
53}p[N];
54
55int main()
56{
57	#ifndef  ONLINE_JUDGE
58	freopen("code/in.txt","r",stdin);
59  #endif
60	cin>>n;
61	ms(dir,-1);
62	for ( int i = 1 ; i <= n+1 ; i++) cin>>p[i].x>>p[i].y;
63	for ( int i = 1 ; i <= n ; i++)
64	{
65	     dir[i] = p[i].getdir(p[i+1]);
66	}
67
68	int ans = 0 ;
69	for ( int i = 1 ; i <= n-1 ; i++)
70	{
71	    if (dir[i]==(dir[i+1]+1)%4) ans++;
72	}
73	cout<<ans<<endl;
74
75  #ifndef ONLINE_JUDGE
76  fclose(stdin);
77  #endif
78    return 0;
79}

以及还有一个O(1)的做法。。太神啦。。。

One can solve this problem in alternative way. Let the answer be equal to x (that means that the number of inner corners of 270 degrees equals x, but the number of inner corners of 90 degrees to n - x). As soon as the sum of the inner corners’ values of polygon of n vertices is equal to 180 × (n - 2), then_x_ × 270 + (n - x) × 90 equals to 180 × (n - 2). This leads us to
, being the answer for the problem calculated in O(1).

相关文章