poj2398

题解:

计算几何入门题

对每个二分最近的在它右边的杆子

如何判断一个杆子在它右边呢

计算机判断这些要更善于利用点积和叉积

如果叉积为正代表在顺时针方向叉积为负在逆时针

发现要在struct里面重载运算符和struct调用struct

就必须要

Point() {}
Point(int x1,int y1)
{
x=x1; y=y1;
}

代码:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define rint register int
#define IL inline
#define rep(i,h,t) for (int i=h;i<=t;i++)
#define dep(i,t,h) for (int i=t;i>=h;i--)
#define me(x) memset(x,0,sizeof(x))
#define mid ((h+t)>>1)
#define ll long long
const int N=1e4;
int n,m,x1,y1,x2,y2,x,y,ans[N],num[N];
struct Point{
int x,y;
Point() {}
Point(int x1,int y1)
{
x=x1; y=y1;
}
Point operator +(const Point &b) const
{
return Point(x+b.x,y+b.y);
}
Point operator -(const Point &b) const
{
return Point(x-b.x,y-b.y);
}
int operator *(const Point &b) const
{
return x*b.x+y*b.y;
}
int operator ^(const Point &b) const
{
return x*b.y-y*b.x;
}
};
struct Line{
Line(){}
Point s,e;
Line(Point s1,Point e1)
{
s=s1,e=e1;
}
}l[N];
bool cmp(Line x,Line y)
{
return x.s.x<y.s.x;
}
IL bool check(Line x,Point y)
{
return ((y-x.s)^(x.e-x.s))<?:;
}
int main()
{
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
ios::sync_with_stdio(false);
while (cin>>n&&n)
{
cin>>m>>x1>>y1>>x2>>y2;
rep(i,,n)
{
cin>>x>>y;
l[i]=Line(Point(x,y1),Point(y,y2));
}
n++;
l[n]=Line(Point(x2,y1),Point(x2,y2));
sort(l+,l+n+,cmp);
me(ans); me(num);
while (m--)
{
cin>>x>>y;
Point p=Point(x,y);
int h=,t=n;
while (h<t)
{
if (check(l[mid],p)) t=mid; else h=mid+;
}
ans[h]++;
}
rep(i,,n) if (ans[i]>) num[ans[i]]++;
cout<<"Box"<<endl;
rep(i,,n)
if (num[i]>) cout<<i<<": "<<num[i]<<endl;
}
return ;
}
上一篇:转换编码utf-8


下一篇:POJ2533——Longest Ordered Subsequence(简单的DP)