首页 > 代码库 > TOYS(计算几何-入门)
TOYS(计算几何-入门)
题目
‘^’代表叉乘
‘?’代表点乘
点积:a?b=ax*bx+ay*by
叉积:a^b=ax*by-bx*ay
有了这些,代码就呼之欲出了。
首先read(线段)
然后read(点)
发现满足二分性(点A一定在前t条线后,在后n-t条线前)
于是,二分优化查找
O(mlogn)
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <vector> #include <cmath> #include <queue> #include <map> #include <set> using namespace std; #define file(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout) inline void read(int &ans){ ans=0;char x=getchar();bool f=0; while(x<‘0‘||x>‘9‘){if(x==‘-‘)f=1;x=getchar();} while(x>=‘0‘&&x<=‘9‘)ans=ans*10+x-‘0‘,x=getchar(); if(f)ans=-ans; } typedef int db;//此题不用开double const int MAXN=5000+10; struct Po{//定义点(向量) db x,y; Po(){}; Po(int x,int y):x(x),y(y){} Po operator-(const Po A)const{return Po(x-A.x,y-A.y);} db operator*(const Po A)const{return x*A.y-y*A.x;} }; int n,m,ans[MAXN],first=true; db X1,Y1,X2,Y2,U[MAXN],L[MAXN]; bool check(Po C,int ID){ Po A=Po(L[ID],Y2); Po B=Po(U[ID],Y1); return (C-A)*(B-A)>0; } int find(db x,db y){ int l=0,r=n+1; while(l<r){ int mid=(l+r)>>1; if(check(Po(x,y),mid))l=mid+1; else r=mid; } return l-1; } db x,y; int main(){ while(scanf("%d",&n)&&n){ if(first)first=false;else if(n)puts(""); memset(ans,0,sizeof(ans)); read(m),read(X1),read(Y1),read(X2),read(Y2); U[n]=L[0]=X1,U[n+1]=L[n+1]=X2; for(int i=1;i<=n;i++)read(U[i]),read(L[i]); for(int i=0;i<m;i++){ read(x),read(y); ans[find(x,y)]++; } for(int i=0;i<=n;i++)printf("%d: %d\n",i,ans[i]); } return 0; }
TOYS(计算几何-入门)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。