C6-定向越野

题目描述

为了锻炼身体，某楠参加了一个定向越野比赛，定向越野是利用地图和指北针导航的一项竞技运动，通常由起点出发，在多个点标处打卡，再返回终点。但是非酋某楠的指北针居然是坏的，所以只能靠记住来时的方向和各个点的坐标来判断下一步。现在希望你能够帮忙判断下一步是左转还是右转。对于每次转弯输出一个字符，左转输出'L'，右转输出'R'，直走不输出。

输入

多组数据输入

每组数据第一行一个数n，n表示按顺序经历的点的数量，包括起点、各个点标以及终点。1

接下来n行每行两个整数为点的坐标，均在INT范围内。

输出

每组数据一行，每次转弯的方向'L'或'R'，中间用空格分隔

输入样例

 5 
 0 0
-1 1
 0 1
-1 2
 0 3

输出样例

R L R

灵魂画手

 坑点1：直走不输出

坑点2 ：int会爆，至少longlong，double最好

代码

#include
#include<string>
#include
#include
#include
#include
using namespace std;
const double eps = 1e-7;

struct Point {
    double x, y;
    Point() {}
    Point(const double &a, const double &b) {
        x = a, y = b;
    }
};
typedef Point Vector;

Point operator -(const Point &a, const Point &b) {
    return Point(a.x - b.x, a.y - b.y);
}

Point operator +(const Point &a, const Point &b) {
    return Point(a.x + b.x, a.y + b.y);
}

double cross(const Point &a, const Point &b) {
    return a.x * b.y - a.y * b.x;
}

double dot(const Point &a, const Point &b) {
    return a.x * b.x + a.y * b.y;
}

double direct(const Point &a, const Point &b, const Point &c) {
    return cross(b - a, c - a);// + Left - Right
}

const int N = 10010;
int n;
long long ans;
Point a[N];

int main() {
    while(cin>>n) {
        for(int i = 0; i < n; ++i) cin>>a[i].x>>a[i].y;
        int L = 0, R = 0;
        for(int i = 2; i < n; ++i) {
            double dir = direct(a[i - 2], a[i - 1], a[i]);
            if(dir > 0) cout<<"L ";
            else if(dir < 0) cout<<"R ";
        }
        cout<<endl;
    }
    return 0;
}
楠助教的算法题解计算几何算法

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

关于tarjan算法的一些整理

【基础】排序算法学习笔记

常用的排序算法介绍和在JAVA的实现（一）

数据结构与算法之PHP查找算法（哈希查找）

数据结构与算法之PHP查找算法（二分查找）

标签