傳送門
計算幾何基礎題——第一題
這個題需要用到的有：
1.向量
2.向量基本運算（加減法）
3.向量叉積
（https://wenku.baidu.com/view/6d53cdcd58f5f61fb73666c6.html）
（http://blog.csdn.net/hc14519/article/details/50716299）
（第一篇是ppt，必須看，講的非常基礎）
（第二篇是關于向量叉積的幾何意義的講解，雖然講的一般，但還是可以看看）
（還有，其實叉積的幾何意義可以說成這樣：
（P×Q就是0,P,Q,P+Q圍成的四邊形的面積，帶符号）
（再補充三個。。）
（http://www.matrix67.com/blog/archives/6217）
（http://www.yalewoo.com/in_triangle_test.html）
（http://blog.sina.com.cn/s/blog_4c70701801013e49.html）
4.二分法
大家學會之後再來做，相信你就會了。
關于如何用叉積判斷點在直線哪一側：
首先要知道怎麼以一個點為坐标原點建立坐标系：
其實隻要将所有向量減去它就好了
然後我們可以用叉積判斷一個點在另一個點的順時針還是逆時針
設向量P,Q（可抽象為坐标系上的點）
Cross(P,Q)<0，則P在Q的逆時針方向
Cross(P,Q)=0，則P,Q在同一直線上
Cross(P,Q)>0，則P在Q的順時針方向
然後利用這個就可以判斷了
然後我們就可以二分了。
代碼：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#define ll long long
using namespace std;
inline int read(){
int x=;char ch=' ';int f=;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')f=-,ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<)+(x<<)+(ch^),ch=getchar();
return x*f;
}
const int N=;
const double eps=;
struct Point{
double x,y;
Point(){}
Point(double _x,double _y):x(_x),y(_y){}
inline Point operator - (const Point& b) const {return Point(x-b.x,y-b.y);}
};
struct Line{
Point s,t;
Line(){}
Line(Point _s,Point _t):s(_s),t(_t){}
}L[N];
inline int dcmp(double x){
if(fabs(x)<eps)return ;
return x>eps?:-;
}
inline double Cross(const Point& a,const Point& b){
return a.x*b.y-a.y*b.x;
}
inline int check(Line L,Point P){
Point P1=L.s-P,P2=L.t-P;
return dcmp(Cross(P1,P2));
}
int n,m,ans[N];
double X1,X2,Y1,Y2;
int main(){
while(){
memset(ans,,sizeof(ans));
n=read();if(!n)break;m=read();
scanf("%lf %lf %lf %lf",&X1,&Y1,&X2,&Y2);
for(int i=;i<=n;i++){
scanf("%lf",&L[i].t.x);L[i].t.y=Y1;
scanf("%lf",&L[i].s.x);L[i].s.y=Y2;
}
for(int i=;i<=m;i++){
Point Ask;scanf("%lf %lf",&Ask.x,&Ask.y);
int l=,r=n,mid;
while(l<r){
mid=(l+r+)>>;
if(check(L[mid],Ask)==-)l=mid;
else r=mid-;
}
ans[l]++;
}
for(int i=;i<=n;i++)printf("%d: %d\n",i,ans[i]);
putchar('\n');
}
return ;
}