comes 2 U

題目描述

為了讓所有選手都感到開(kāi)心，Nowcoder練習(xí)賽總會(huì)包含一些非?；镜膯?wèn)題。 比如說(shuō)：
按順時(shí)針或逆時(shí)針?lè)较蚪o你一個(gè)簡(jiǎn)單的多邊形的頂點(diǎn)坐標(biāo)，請(qǐng)回答此多邊形是順時(shí)針還是逆時(shí)針。

輸入描述:

輸入包含N + 1行。
第一行包含一個(gè)整數(shù)N，表示簡(jiǎn)單多邊形的頂點(diǎn)數(shù)。
在下面的N行中，第i行包含兩個(gè)整數(shù)xi，yi，表示簡(jiǎn)單多邊形中的第i個(gè)頂點(diǎn)的坐標(biāo)。

輸出描述:

如果簡(jiǎn)單多邊形按順時(shí)針順序給出，則在一行中輸出“clockwise”（不帶引號(hào)）。 否則，打印”counterclockwise”（不帶引號(hào)）。

示例1

輸入

3
0 0
1 0
0 1

輸出

counterclockwise

示例2

輸入

3
0 0
0 1
1 0

輸出

clockwise

備注:

3≤N≤30
-1000≤xi，yi≤1000
數(shù)據(jù)保證，這個(gè)簡(jiǎn)單多邊形的面積不為零。

思路

Green公式：https://blog.csdn.net/henuyh/article/details/80378818

叉積判斷
多邊形可能是凹多邊形，所以要統(tǒng)計(jì)叉積正負(fù)的數(shù)量。如果正數(shù)多逆時(shí)針，負(fù)數(shù)多順時(shí)針。

AC

//Green公式 #include<bits/stdc++.h> #define N 100005 using namespace std; struct ac {int x, y; }a[N]; int main() { // freopen("in.txt", "r", stdin);int n;while (scanf("%d", &n) != EOF) {for (int i = 0; i < n;i ++) {scanf("%d%d", &a[i].x, &a[i].y);}double d = 0;for (int i = 0; i < n - 1; i++) {d += -0.5 * (a[i].y + a[i + 1].y) * (a[i + 1].x - a[i].x); }if (d < 0) cout << "clockwise\n";else cout << "counterclockwise\n"; }return 0; } //計(jì)算叉積 #include<bits/stdc++.h> #define ll long long #define N 100005 using namespace std; struct ac {int x, y; }a[N]; //計(jì)算叉積 int cross_product(ac a, ac b, ac c) {int x1 = b.x - a.x;int y1 = b.y - a.y;int x2 = c.x - b.x;int y2 = c.y - b.y;return x1 * y2 - x2 * y1; } int main() { // freopen("in.txt", "r", stdin);int n;while (scanf("%d", &n) != EOF) {for (int i = 0; i < n;i ++) {scanf("%d%d", &a[i].x, &a[i].y);}//統(tǒng)計(jì)正負(fù)值數(shù)量 int integer = 0, negative = 0;for (int i = 0; i < n - 2; i++) {int t = cross_product(a[i], a[i + 1], a[i + 2]);if (t > 0) integer++;if (t < 0) negative++;}if (integer < negative) cout << "clockwise\n";else cout << "counterclockwise\n"; }return 0; }

總結(jié)

以上是生活随笔為你收集整理的B 简单多边形的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。