遮挡判断
Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 659 Accepted Submission(s): 197
Problem Description
在一个广场上有一排沿着东西方向排列的石柱子，阳光从东边以一定的倾角射来（平行光）。有的柱子可能被在他东边的高大的柱子的影子给完全遮挡住了。现在你要解决的问题是求出有多少柱子是没有被完全遮挡住的。
假设每个石柱子是一根细棒，而且都垂直于地面摆放。
Input
输入包含多组数据。每组数据第一行是一个整数N(0
Output
对每组数据，输出包含所求数目的一行。
Sample Input
4
0 3
3 1
2 2
1 1
1/1
0
Sample Output
2
提示：
输入数据很多，请用scanf代替cin。
Source
UESTC 6th Programming Contest Online
Recommend
lcy
思路： 每个柱子都会在x轴上映射出一个区间 那么只要看被包含的区间有多少个 用总的减去被包含的区间的个数即可
[cpp]
#include
#include
#include
struct haha
{
double s;
double h;
double e;
}a[111111];
//bool vis[10000000+100];
int cmp(const void *a,const void *b)
{
return (*(struct haha *)a).s>(*(struct haha *)b).s 1:-1;
}
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
if(!n) break;
double tan,c,b;
for(i=0;i
scanf("%lf/%lf",&c,&b);
tan=c/b;
//printf("%lf\n",tan);
qsort(a,n,sizeof(a[0]),cmp);
for(i=0;i
a[i].e=a[i].s+a[i].h/tan;
// printf("s=%lf e=%lf\n",a[i].s,a[i].e);
}
int cnt=n;
double s,e;
s=a[0].s;e=a[0].e;
for(i=1;i
if(a[i].e<=e&&a[i].s>=s) cnt--;
else
{
if(a[i].e>e) {e=a[i].e;s=a[i].s;}
}
}
printf("%d\n",cnt);
}
return 0;
}
#include
#include
#include
struct haha
{
double s;
double h;
double e;
}a[111111];
//bool vis[10000000+100];
int cmp(const void *a,const void *b)
{
return (*(struct haha *)a).s>(*(struct haha *)b).s 1:-1;
}
int main()
{
int n,i,j;
while(scanf("%d",&n)!=EOF)
{
if(!n) break;
double tan,c,b;
for(i=0;i
scanf("%lf/%lf",&c,&b);
tan=c/b;
//printf("%lf\n",tan);
qsort(a,n,sizeof(a[0]),cmp);
for(i=0;i
a[i].e=a[i].s+a[i].h/tan;
// printf("s=%lf e=%lf\n",a[i].s,a[i].e);
}
int cnt=n;
double s,e;
s=a[0].s;e=a[0].e;
for(i=1;i
if(a[i].e<=e&&a[i].s>=s) cnt--;
else
{
if(a[i].e>e) {e=a[i].e;s=a[i].s;}
}
}
printf("%d\n",cnt);
}
return 0;
}