1246. Tethered Dog
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
A dog is tethered to a pole with a rope. The pole is located inside a fenced polygon (not necessarily convex) with nonzero area. The fence has no self-crosses. The Olympian runs along the fence bypassing the vertices of the polygon in a certain order which is not broken during the jog. A dog pursues him inside the fenced territory and barks. Your program is to determine how (clockwise or counter-clockwise) the rope will wind after several rounds of the Olympian's jog.
Input
The first input line contains a number N that is the number of the polygon vertices. It’s known that 3 ≤ N ≤ 200000. The next N lines consist of the vertices plane coordinates, given in an order of Olympian’s dog. The coordinates are a pair of integers separated with a space. The absolute value of each coordinate doesn’t exceed 50000.
Output
You are to output "cw", if the rope is winded in a clockwise order and "ccw" otherwise.
Sample
| input | output |
|---|---|
4 |
cw |
Problem Author: Evgeny Kobzev
Problem Source: Ural State University Personal Programming Contest, March 1, 2003
Problem Source: Ural State University Personal Programming Contest, March 1, 2003
Difficulty: 364
题意：问一个多边形的给出顺序是不是顺时针。
分析：叉积判断方向。用最左或最优的点作为基准点。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef double DB;
#define For(i, s, t) for(int i = (s); i <= (t); i++)
#define Ford(i, s, t) for(int i = (s); i >= (t); i--)
#define Rep(i, t) for(int i = (0); i < (t); i++)
#define Repn(i, t) for(int i = ((t)-1); i >= (0); i--)
#define rep(i, x, t) for(int i = (x); i < (t); i++)
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair
inline void SetIO(string Name)
{
string Input = Name+".in",
Output = Name+".out";
freopen(Input.c_str(), "r", stdin),
freopen(Output.c_str(), "w", stdout);
} inline int Getint()
{
int Ret = ;
char Ch = ' ';
bool Flag = ;
while(!(Ch >= '' && Ch <= ''))
{
if(Ch == '-') Flag ^= ;
Ch = getchar();
}
while(Ch >= '' && Ch <= '')
{
Ret = Ret * + Ch - '';
Ch = getchar();
}
return Flag ? -Ret : Ret;
} const int N = ;
struct Point
{
DB x, y;
inline void Read()
{
scanf("%lf%lf", &x, &y);
}
} Arr[N];
int n; inline void Input()
{
scanf("%d", &n);
For(i, , n) Arr[i].Read();
} inline DB Det(const Point &A, const Point &O, const Point &B)
{
DB X1 = A.x - O.x, X2 = B.x - O.x;
DB Y1 = A.y - O.y, Y2 = B.y - O.y;
return X1 * Y2 - X2 * Y1;
} inline void Solve()
{
int p = ;
For(i, , n)
if(Arr[i].x > Arr[p].x) p = i;
Arr[] = Arr[n], Arr[n + ] = Arr[];
if(Det(Arr[p - ], Arr[p], Arr[p + ]) >= 0.0) puts("cw");
else puts("ccw");
} int main()
{
#ifndef ONLINE_JUDGE
SetIO("E");
#endif
Input();
Solve();
return ;
}