Counter-Clockwise

For given three points p0,p1,p2, print

1	COUNTER_CLOCKWISE

if p0,p1,p2 make a counterclockwise turn (1),

CLOCKWISE

if p0,p1,p2 make a clockwise turn (2),

1	ONLINE_BACK

if p2 is on a line p2,p0,p1 in this order (3),

1	ONLINE_FRONT

if p2 is on a line p0,p1,p2 in this order (4),

1	ON_SEGMENT

if p2 is on a segment p0p1 (5).

Input

xp0 yp0 xp1 yp1
q
xp20 yp20
xp21 yp21
...
xp2q−1 yp2q−1

In the first line, integer coordinates of p0 and p1 are given. Then, q queries are given for integer coordinates of p2.

Output

For each query, print the above mentioned status.

Constraints

1≤q≤1000
−10000≤xi,yi≤10000
p0 and p1 are not identical.

Sample Input 1

Sample Output 1

1 2	COUNTER_CLOCKWISE CLOCKWISE

Sample Input 2

Sample Output 2

1
2
3

ONLINE_BACK
ON_SEGMENT
ONLINE_FRONT

Source: https://onlinejudge.u-aizu.ac.jp/problems/CGL_1_C

就是判断三个点的位置关系，用叉积和点积就够了。

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
};
typedef Point Vector;
Vector operator + (Vector A,Vector B){
    return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
    return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double p){
    return Vector(A.x*p,A.y*p);
}
Vector operator / (Vector A,double p){
    return Vector(A.x/p,A.y/p);
}
bool operator < (const Point& a,const Point& b){
    return a.x<b.x||(a.x==b.x&&a.y<b.y);
}
const double eps = 1e-10;
int dcmp(double x){
    if(fabs(x)<eps) return 0; else return (x<0?-1:1);
}
bool operator == (const Point& a,const Point& b){
    return dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)==0;
}
//点积
double Dot(Vector A,Vector B){
    return A.x*B.x+A.y*B.y;
}
double Length(Vector A){
    return sqrt(Dot(A,A));
}
double Angle(Vector A,Vector B){
    return acos(Dot(A,B)/Length(A)/Length(B));
}
 
//叉积
double Cross(Vector A,Vector B){
    return (A.x*B.y-A.y*B.x);
}
//三角形面积的二倍的叉乘公式
double Area2(Point A,Point B,Point C){
    return Cross(B-A,C-A);
}
//向量旋转,rad是弧度
Vector Rotate(Vector A,double rad){
    return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
}
//计算向量的单位法线,先逆时针旋转90度，然后把长度归一化
Vector Normal(Vector A){
    double Len=Length(A);
    return Vector(-A.y/Len,A.x/Len);
}
//求两直线交点
//调用前请确保P+tv和Q+tw有唯一交点，当且仅当Cross(v,w)非0
Point GetLineIntersection(Point P,Vector v,Point Q,Vector w){
    Vector u=P-Q;
    double t=Cross(w,u)/Cross(v,w);
    return P+v*t;
}
//点到直线的距离
double DistanceToLine(Point P,Point A,Point B){
    Vector v1=B-A,v2=P-A;
    return fabs(Cross(v1,v2))/Length(v1);
}
//点到线段的距离
double DistanceToSegment(Point P,Point A,Point B){
    if(A==B) return Length(P-A);
    Vector v1=B-A,v2=P-A,v3=P-B;
    if(dcmp(Dot(v1,v2))<0) return Length(v2);
    else if(dcmp(Dot(v1,v3))>0) return Length(v3);
    else return fabs(Cross(v1,v2))/Length(v1);
}
//点在直线上的投影
Point GetLineProjection(Point P,Point A,Point B){
    Vector v=B-A;
    return A+v*(Dot(v,P-A)/Dot(v,v));
}
Point GetLineReflection(Point P,Point A,Point B){
    return GetLineProjection(P,A,B)*2-P;
}
int main(){
    Point A,B;
    cin>>A.x>>A.y>>B.x>>B.y;
    int t;
    cin>>t;
    while(t--){
        Point P;
        cin>>P.x>>P.y;
        double cro=Cross(B-A,P-A);
        double dot=Dot(B-A,P-A);
        double dot2=Dot(A-B,P-B);
        if(dcmp(cro)<0){
            cout<<"CLOCKWISE";
        }else if(dcmp(cro)>0){
            cout<<"COUNTER_CLOCKWISE";
        }else{
            if(dcmp(dot)<0){
                cout<<"ONLINE_BACK";
            }else{
                if(dcmp(dot2)<0){
                    cout<<"ONLINE_FRONT";
                }else{
                    cout<<"ON_SEGMENT";
                }
            }
        }
        cout<<"\n";
    }
    return 0;
}

pyai's blog

CGL_1_C: Counter-Clockwise