360K 172MS

二分法和叉積

代碼如下

?

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int n,m;
double x1,y1,x2,y2;
struct point
{
?? ?double x;
?? ?double y;
};
struct T
{
?? ?point a;
?? ?point b;//a點在b點上方
}line[5500];
int res[5500];
point temp;
bool check(point p,T lin)//判斷p點在lin的左方返回true，在lin的右方返回false
{
?? ?double cc=(lin.a.x-lin.b.x)*(p.y-lin.b.y)-(lin.a.y-lin.b.y)*(p.x-lin.b.x);
?? ?if(cc>0)
?? ?{
?? ??? ?return true;
?? ?}
?? ?return false;
}
void run(int l,int r)
{
?? ?if(r-l==1)
?? ?{
?? ??? ?res[r]++;
?? ??? ?return;
?? ?}
?? ?int mid=(l+r)/2;
?? ?if(check(temp,line[mid]))//temp在給定線段左邊
?? ?{
?? ??? ?run(l,mid);
?? ?}
?? ?else
?? ?{
?? ??? ?run(mid,r);
?? ?}
}
int main()
{
?? ?while(scanf("%d",&n),n)
?? ?{
?? ??? ?scanf("%d %lf %lf %lf %lf",&m,&x1,&y1,&x2,&y2);
?? ??? ?int i;
?? ??? ?for(i=0;i<=n;i++)
?? ??? ?{
?? ??? ??? ?res[i]=0;
?? ??? ?}
?? ??? ?for(i=0;i<n;i++)
?? ??? ?{
?? ??? ??? ?scanf("%lf %lf",&line[i].a.x,&line[i].b.x);
?? ??? ??? ?line[i].a.y=y1;
?? ??? ??? ?line[i].b.y=y2;
?? ??? ?}
?? ??? ?//T left,right;
?? ??? ?//left.a.x=x1;
?? ??? ?//left.a.y=y1;
?? ??? ?//left.b.x=x1;
?? ??? ?//left.b.y=y2;
?? ??? ?//right.a.x=x2;
?? ??? ?//right.a.y=y1;
?? ??? ?//right.b.x=x2;
?? ??? ?//right.b.y=y2;
?? ??? ?for(i=0;i<m;i++)
?? ??? ?{
?? ??? ??? ?scanf("%lf %lf",&temp.x,&temp.y);
?? ??? ??? ?if(check(temp,line[0]))
?? ??? ??? ?{
?? ??? ??? ??? ?res[0]++;
?? ??? ??? ??? ?continue;
?? ??? ??? ?}
?? ??? ??? ?if(check(temp,line[n-1])==false)
?? ??? ??? ?{
?? ??? ??? ??? ?res[n]++;
?? ??? ??? ??? ?continue;
?? ??? ??? ?}
?? ??? ??? ?run(0,n);
?? ??? ?}
?? ??? ?for(i=0;i<=n;i++)
?? ??? ?{
?? ??? ??? ?printf("%d: %d\n",i,res[i]);
?? ??? ?}
?? ??? ?printf("\n");
?? ?}
?? ?return 0;
}

轉載于:https://www.cnblogs.com/willzhang/archive/2012/07/15/2592762.html

總結

以上是生活随笔為你收集整理的poj2318 TOYS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。