數(shù)學(xué)集：點(diǎn)與線
模版前導(dǎo)：
struct Point{
double x,y;
}p[N];
//點(diǎ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|,計(jì)算夾角
double angle(Point a,Point b){
return acos(dota,b)/len(a)/len(b));
}
//>0,點(diǎn)在線的左側(cè)
//=0,點(diǎn)在線上
//<0,點(diǎn)在線的右側(cè)
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)
//線段無交點(diǎn):>0
//線段有交點(diǎn):<=0
//兩條線段:
cross(a,b,c)*cross(a,b,d)>0
//&
cross(c,d,a)*cross(c,d,b)>0
//無交點(diǎn)
//求交點(diǎn)
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，分別是圓心的坐標(biāo)及半徑，接下來有n個點(diǎn)，每次給你點(diǎn)的坐標(biāo)，求以圓心為中心的半圓最多能覆蓋多少個點(diǎn)。
解題思路：
拿到本題首先考慮滿足因素，先判斷有多少個點(diǎn)在圓內(nèi)，再將處于圓內(nèi)的點(diǎn)提取出來，依次遍歷每個點(diǎn)與圓心作為線時(shí)（點(diǎn)的數(shù)據(jù)量為1000，不會超時(shí)），有多少點(diǎn)能被覆蓋，這里就需要用到叉積的性質(zhì)來判斷點(diǎn)與線的位置。
#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;
//點(diǎn)的結(jié)構(gòu)體
struct Point{
double x,y;
}o,p[N],a;
//兩點(diǎn)間距離公式
double dis(Point a,Point b){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
//計(jì)算叉積
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;
//在圓內(nèi)就放入
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++)
{
//當(dāng)點(diǎn)在線的左側(cè)或在線上時(shí)，記錄該點(diǎn)
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(題目中因?yàn)閤1,y1導(dǎo)致編程錯誤，所以在實(shí)際題目中更改了變量名)，x1,y1為矩陣的左上坐標(biāo)，x2,y2為矩陣的右下坐標(biāo),接下來n行，每次給你分割區(qū)間的上下兩個坐標(biāo)，即每次給你的都是x軸坐標(biāo)，y軸坐標(biāo)都是固定的，接下來m行，每次給你兩個坐標(biāo)表示玩具的個數(shù)，矩陣被線段分割的每個區(qū)間中有多少玩具。
解題思路：
既然要判斷每個區(qū)間有多少玩具，這里用叉積的點(diǎn)線判斷后，就變成單純的二分問題了，剩下的難點(diǎn)估計(jì)就是點(diǎn)的記錄，太繞了。
#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;
//叉積公式，判斷點(diǎn)在線的那一端
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);
}
//數(shù)據(jù)量點(diǎn)有5000,線有5000，必須要有優(yōu)化
//二分查找
int find(Point o){
int l=-1,r=n+1;
while(l+1<r)
{
int mid=l+(r-l)/2;
//當(dāng)叉積小于等于0時(shí)點(diǎn)在線的右側(cè)或在線上
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;
//左邊區(qū)間頂點(diǎn)
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;
//在那個區(qū)間就加在哪里
ans[find(o)]++;
}
if (!flag)flag=1;
else cout <<"\n";
for (int i=0;i<=n;i++)cout <<i<<": "<<ans[i]<<"\n";
}
return 0;
}
查看12道真題和解析