遮擋判斷
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<N<=100000)，表示柱子的個數。N=0代表輸入結束。接下來有N行，每行是兩個整數，分別給出每根柱子的水平位置X和高度H（X越大，表示越在西邊，0<=X<=10000000,0<H<=10000000保證不會有兩根柱子在同一個X坐標上）。最後有一行，以分數的形式給出太陽光與地面的夾角的正切值T/A(1<=A,T<=10)。
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<stdio.h>
#include<string.h>
#include<stdlib.h>
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<n;i++)
scanf("%lf %lf",&a[i].s,&a[i].h);
scanf("%lf/%lf",&c,&b);
tan=c/b;
//printf("%lf\n",tan);
qsort(a,n,sizeof(a[0]),cmp);
for(i=0;i<n;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<n;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<stdio.h>
#include<string.h>
#include<stdlib.h>
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<n;i++)
scanf("%lf %lf",&a[i].s,&a[i].h);
scanf("%lf/%lf",&c,&b);
tan=c/b;
//printf("%lf\n",tan);
qsort(a,n,sizeof(a[0]),cmp);
for(i=0;i<n;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<n;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;
}
