poj2318

我的代码

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iostream>
#define int long long
#define db double
#define inf 1e18
#define gc getchar
#define pc putchar
#define lowbit(x) (x)&(-(x))
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=gc();
	while(!isdigit(ch))
	{
		if(ch=='-')
			f=-f;
		ch=gc();
	}
	while(isdigit(ch))
		x=(x<<3)+(x<<1)+ch-'0',ch=gc();
	return x*f;
}
inline void write(int x)
{
	if(x<0)
		pc('-'),x=-x;
	if(x>9)
		write(x/10);
	pc(x%10+'0');
	return;
}
const int N=5140;
const db eps=1e-4;
inline int sgn(db x)
{
	if(fabs(x)<eps)
		return 0;
	return x<0?-1:1;
}
struct Point{
	db x,y;
	Point(){}
	Point(db x, db y):x(x),y(y){}
	Point operator + (Point B){return Point(x+B.x,y+B.y);}
	Point operator - (Point B){return Point(x-B.x,y-B.y);}
	Point operator * (db k){return Point(x*k,y*k);}
	Point operator / (db k){return Point(x/k,y/k);}
	bool operator == (Point B){return sgn(x-B.x)==0&&sgn(y-B.y)==0;}
}point[N];
struct Line{
	Point p1,p2;
	Line(){}
	Line(Point p1, Point p2):p1(p1),p2(p2){}
}line[N];
typedef Point Vector;
db Cross(Vector A, Vector B){return A.x*B.y-A.y*B.x;}
int Relation(Point p, Line v)
{
	int c=sgn(Cross(v.p1-p,v.p2-p));
	if(c<0)
		return 1;//left
	if(c>0)
		return 2;//right
	return 0;//on
}
signed main()
{
//	freopen("114514.in","r",stdin);
//	freopen("114514.out","w",stdout);
	bool flag=1;
	int n;
	while(n=read())
	{
		if(flag)
			flag=0;
		else
			puts(""),puts("");
		int m=read();
		Point a,b;
		a.x=db(read()),a.y=db(read());
		b.x=db(read()),b.y=db(read());
		line[n]=Line(Point(a.x,b.y),b); 
		for(int i=0;i<n;i++)
		{
			Point p1,p2;
			p1.x=db(read()),p2.x=db(read());
			p1.y=a.y,p2.y=b.y;
			line[i]=Line(p1,p2);
		}
		int ans[N]={0};
		for(int i=1;i<=m;i++)
		{
			point[i].x=db(read());
			point[i].y=db(read());
			int l=0,r=n;
			while(l<r)
			{
				int mid=l+r>>1;
				if(Relation(point[i],line[mid])==1)
					r=mid;	
				else
					l=mid+1;	
			}
			ans[r]++;
		}
		for(int i=0;i<=n;i++)
		{
			printf("%d: %d",i,ans[i]);
			if(i!=n)
				puts("");
		}
	}
	return 0;	
}

正解（网上找的题解）

#include<cstdio>
#include<queue>
#include<cctype>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int K=5005;
typedef double dl;
inline int read(){
    int X=0,w=0;char ch=0;
    while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
    while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
    return w?-X:X;
}
struct point{
    int x;
    int y;
}q;
struct line{
    int u;
    int l;
}p[K];
int n,m,x1,y1,x2,y2,ans[K];
inline point getmag(point a,point b){
    point s;
    s.x=b.x-a.x;s.y=b.y-a.y;
    return s;
}
inline int multiX(point a,point b){
    return a.x*b.y-b.x*a.y;
}
int erfen(int l,int r){
    if(l==r)return l-1;
    int mid=(l+r)>>1;
    point a,b;w
    a.x=p[mid].u;a.y=y1;
    b.x=p[mid].l;b.y=y2;
    if(multiX(getmag(q,a),getmag(q,b))<0)return erfen(l,mid);
    return erfen(mid+1,r);
}
int main(){
    bool first=0;
    while(scanf("%d",&n)!=EOF&&n){
    if(first)putchar('\n');
    first=1;
    memset(ans,0,sizeof(ans));
    int m=read();
    x1=read();y1=read();
    x2=read();y2=read();
    for(int i=1;i<=n;i++){
        p[i].u=read();
        p[i].l=read();
    }
    for(int i=1;i<=m;i++){
        q.x=read();
        q.y=read();
        ans[erfen(1,n+1)]++;
    }
    for(int i=0;i<=n;i++){
        printf("%d: %d\n",i,ans[i]);
    }
    }
    return 0;
}