数学集：点与线

模版前导：

struct Point{
	double x,y;
}p[N];

//点积代码
//a*b=0,两向量垂直
//a*b==|a||b|,两向量平行
double dot(Point a,Point b){
  return a.x*b.x+a.y*b.y;
}
//求模长
double len(Point a){
  return sqrt(a.x*a.x+a.y+a.y);
}
//a*b/|a||b|,计算夹角
double angle(Point a,Point b){
  return acos(dota,b)/len(a)/len(b));
}

//>0,点在线的左侧
//=0,点在线上
//<0,点在线的右侧
double cross(Point a,Point b,Point c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

//x换first
//y换second
typedef pair<double, double> Point;

Point operator-(const Point& a,const Point& b){
	return Point(a.first-b.first,a.second-b.second);
}

Point operator+(const Point& a,const Point& b){
	return Point(a.first+b.first,a.second+b.second);
}

Point operator*(const Point& a,const double& t){
	return Point(a.first*t,a.second*t);
}

double operator*(const Point& a,const Point& b){
	return a.first*b.second-a.second*b.first;
}

//直线和线段:
cross(a,b,c)*cross(a,b,d)
//线段无交点:>0
//线段有交点:<=0
//两条线段:
cross(a,b,c)*cross(a,b,d)>0
//&
cross(c,d,a)*cross(c,d,b)>0
//无交点
  
//求交点
Point getNode(Point a,Point b,Point c,Point d){
	double t=(a-c)*d/(d*b);
  	return a+b*t;
}

题目一：

原题链接：Transmitters

题意：

题目存在多组输入，先给你三个值x,y,r，分别是圆心的坐标及半径，接下来有n个点，每次给你点的坐标，求以圆心为中心的半圆最多能覆盖多少个点。

解题思路：

拿到本题首先考虑满足因素，先判断有多少个点在圆内，再将处于圆内的点提取出来，依次遍历每个点与圆心作为线时（点的数据量为1000，不会超时），有多少点能被覆盖，这里就需要用到叉积的性质来判断点与线的位置。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<bitset>
#include<map>
#include<queue>
#include<stack>

#define FAST_READ                        \
    ios::sync_with_stdio(0), cin.tie(0); \
cout.tie(0);
using namespace std;

const int N=1e6+10;

int t;
double r;
//点的结构体
struct Point{
	double x,y;
}o,p[N],a;
//两点间距离公式
double dis(Point a,Point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
//计算叉积
double cross(Point a,Point b,Point c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}

int main()
{
	FAST_READ; 
	while(cin >>o.x>>o.y>>r)
	{
		if (r<0)return 0;
		cin >>t;
		int top=0,maxn=0;
		while(t--)
		{
			cin >>a.x>>a.y;
		  //在圆内就放入
			if (dis(a,o)<=r)p[top++]=a;
		}
		for (int i=0;i<top;i++)
		{
			int cnt=0;
			for (int j=0;j<top;j++)
			{
			  //当点在线的左侧或在线上时，记录该点
				if (cross(o,p[i],p[j])>=0)cnt++;
			}
			maxn=max(maxn,cnt);
		}
		cout <<maxn<<"\n";
	} 
	return 0;
}

题目二：

原题链接：TOYS

题意：

题目存在多组输入，先给你六个值，n,m,x1,y1,x2,y2(题目中因为x1,y1导致编程错误，所以在实际题目中更改了变量名)，x1,y1为矩阵的左上坐标，x2,y2为矩阵的右下坐标,接下来n行，每次给你分割区间的上下两个坐标，即每次给你的都是x轴坐标，y轴坐标都是固定的，接下来m行，每次给你两个坐标表示玩具的个数，矩阵被线段分割的每个区间中有多少玩具。

解题思路：

既然要判断每个区间有多少玩具，这里用叉积的点线判断后，就变成单纯的二分问题了，剩下的难点估计就是点的记录，太绕了。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<bitset>
#include<map>
#include<queue>
#include<stack>

#define FAST_READ                        \
    ios::sync_with_stdio(0), cin.tie(0); \
cout.tie(0);
using namespace std;

const int N=1e6+10;

int n,m,u,l;
double lx,rx,ly,ry;
int ans[N];
struct Point{
	double x,y;
}a[N],b[N],o;
//叉积公式，判断点在线的那一端 
double cross(Point a,Point b,Point c){
	return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
}
//数据量点有5000,线有5000，必须要有优化
//二分查找 
int find(Point o){
	int l=-1,r=n+1;
	while(l+1<r)
	{
		int mid=l+(r-l)/2;
		//当叉积小于等于0时点在线的右侧或在线上 
		if (cross(b[mid],a[mid],o)<=0)l=mid;
		else r=mid;
	}
	return l;
}

int main()
{
	FAST_READ; 
	bool flag=0;
	while(cin >>n)
	{
		if (n==0)return 0;
		cin >>m>>lx>>ly>>rx>>ry;
		//左边区间顶点 
		a[0].x=b[0].x=lx;
		a[0].y=ly;
		b[0].y=ry;
		for (int i=1;i<=n;i++)
		{
			cin >>u>>l;
			//记录每条线 
			a[i].x=u;
			a[i].y=ly;
			b[i].x=l;
			b[i].y=ry;
		}
		//初始化记录的ans 
		for (int i=0;i<=n;i++)ans[i]=0;
		while(m--)
		{
			cin >>o.x>>o.y;
			//在那个区间就加在哪里 
			ans[find(o)]++;
		}
		if (!flag)flag=1;
		else cout <<"\n";
		for (int i=0;i<=n;i++)cout <<i<<": "<<ans[i]<<"\n";
	}
	return 0;
}