| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 624 人关注过本帖
标题:[求助]是个关于坐标上点与图形关系的问题
只看楼主 加入收藏
kakawei
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2007-10-29
收藏
 问题点数:0 回复次数:2 
[求助]是个关于坐标上点与图形关系的问题

这是我的一个作业后面是我编的题目,结果超时了,为什么啊?

汤姆的游戏

Time limit:5000 ms Memory limit:65535 KB
Total Submit:122 (30 users) Accepted Submit:2 (1 users)

Description

汤姆是个好动的孩子,今天他突然对圆规和直尺来了兴趣。于是他开始在一张很大很大的白纸上画很多很多的矩形和圆。画着画着,一不小心将他的爆米花弄撒了, 于是白纸上就多了好多好多的爆米花。汤姆发现爆米花在白纸上看起来就像一个个点,有些点落在矩形或圆内部,而有些则在外面。于是汤姆开始数每个点在多少个 矩形或圆内部。毕竟汤姆还只是个孩子,而且点、矩形和圆又非常多。所以汤姆数了好一会都数不清,于是就向聪明的你求助了。你的任务是:在给定平面上N个图 形(矩形或圆)以及M个点后,请你求出每个点在多少个矩形或圆内部(这里假设矩形的边都平行于坐标轴)。

Input

多组测试数据 每组第一行为两个正整数N和M,其中N表示有多少个图形(矩形或圆),M表示有多少个点。接下来的N行是对每个图形的描述,具体来说,第i+1行表示第i 个图形。先是一个字母,若该字母为“r”,则表示该图形是一个矩形,这时后面将有4个实数x1,y1,x2,y2,表示该矩形的一对对角顶点的坐标分别为 (x1,y1)和(x2,y2);若该字母为“c”,则表示该图形是一个圆,这时后面将有3个实数x,y,r,表示该圆以(x,y)为圆心并以r为半径。 最后M行是对每个点的描述,其中每行将有两个实数x,y,表示一个坐标为(x,y)的点。读到0 0 时结束 。

Output

每组包含M行,每行是一个整数,其中第i行的整数表示第i个点在多少个图形内部(当某点在一个图形的边界上时,我们认为该点不在这个图形的内部)。

Sample Input

3 4
r 1.015 0.750 5.000 4.000
c 6.000 5.000 2.020
r 6.500 7.200 7.800 9.200
3.500 2.500
4.995 3.990
2.300 8.150
6.900 8.000
0 0

Sample Output

1
2
0
1




#include<iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;

while(n!=0&&m!=0)
{int counter[m];
for(int i=0;i<m;i++)
counter[i]=0;
double x1[n];double y1[n];
double r[n];double x2[n];
double y2[n];double x0[n];
double y0[n];double x[m];double y[m];

for(int i=0;i<n;i++)
{
char tu;
cin>>tu;
if(tu=='r')
{
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
}
if(tu=='c')
{
cin>>x0[i]>>y0[i]>>r[i];
}
}
for(int i=0;i<m;i++)
{
cin>>x[i]>>y[i];
}

for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if((x[i]<x1[j]&&x[i]>x2[j]&&y[i]<y1[j]&&y[i]>y2[j])||(x[i]>x1[j]&&x[i]<x2[j]&&y[i]>y1[j]&&y[i]<y2[j]))
counter[i]+=1;
else if((x[i]<x1[j]&&x[i]>x2[j]&&y[i]>y1[j]&&y[i]<y2[j])||(x[i]>x1[j]&&x[i]<x2[j]&&y[i]<y1[j]&&y[i]>y2[j]))
counter[i]+=1;
if((x[i]-x0[j])*(x[i]-x0[j])+(y[i]-y0[j])*(y[i]-y0[j])<r[j]*r[j])
counter[i]+=1;
}
cout<<counter[i]<<endl;
}
cin>>n>>m;
}
system("pause");
}

搜索更多相关主题的帖子: 图形 坐标 div 
2007-11-07 12:06
kakawei
Rank: 1
等 级:新手上路
帖 子:33
专家分:0
注 册:2007-10-29
收藏
得分:0 
我改了一下,还是超时为什么啊!?
#include<iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;

while(n!=0&&m!=0)
{
int counter[m];
for(int i=0;i<m;i++)
counter[i]=0;
double x1[n];double y1[n];
double r[n];double x2[n];
double y2[n];double x0[n];
double y0[n];double x[m];double y[m];

for(int i=0;i<n;i++)
{
char tu;
cin>>tu;
if(tu=='r')
{
cin>>x1[i]>>y1[i]>>x2[i]>>y2[i];
}
if(tu=='c')
{
cin>>x0[i]>>y0[i]>>r[i];
}
}
for(int i=0;i<m;i++)
{
cin>>x[i]>>y[i];
}

for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if((x[i]-x1[j])*(x[i]-x2[j])<0&&(y[i]-y1[j])*(y[i]-y2[j])<0)
counter[i]+=1;
if((x[i]-x0[j])*(x[i]-x0[j])+(y[i]-y0[j])*(y[i]-y0[j])<r[j]*r[j])
counter[i]+=1;
}
cout<<counter[i]<<endl;
}
cin>>n>>m;
}
system("pause");
}


乱舞风云
2007-11-07 17:01
拉风
Rank: 1
等 级:新手上路
帖 子:22
专家分:0
注 册:2007-11-7
收藏
得分:0 
#include<iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;

while(n!=0&&m!=0)
{
int counter[m];
晕啊,有你这样定义数组的吗?你的又不是动态数组

一切都是从菜鸟开始的
2007-11-10 23:18
快速回复:[求助]是个关于坐标上点与图形关系的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.014896 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved