首页 > 代码库 > HDU 5033 Building(类凸包+向量叉积的应用)

HDU 5033 Building(类凸包+向量叉积的应用)

2024-07-24 05:23:37   223人阅读

Building

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1138    Accepted Submission(s): 321
Special Judge

Problem Description
Once upon a time Matt went to a small town. The town was so small and narrow that he can regard the town as a pivot. There were some skyscrapers in the town, each located at position xi with its height hi. All skyscrapers located in different place. The skyscrapers had no width, to make it simple. As the skyscrapers were so high, Matt could hardly see the sky.Given the position Matt was at, he wanted to know how large the angle range was where he could see the sky. Assume that Matt‘s height is 0. It‘s guaranteed that for each query, there is at least one building on both Matt‘s left and right, and no building locate at his position.
 

Input
The first line of the input contains an integer T, denoting the number of testcases. Then T test cases follow.

Each test case begins with a number N(1<=N<=10^5), the number of buildings.

In the following N lines, each line contains two numbers, xi(1<=xi<=10^7) and hi(1<=hi<=10^7).

After that, there‘s a number Q(1<=Q<=10^5) for the number of queries.

In the following Q lines, each line contains one number qi, which is the position Matt was at.
 

Output
For each test case, first output one line "Case #x:", where x is the case number (starting from 1).

Then for each query, you should output the angle range Matt could see the sky in degrees. The relative error of the answer should be no more than 10^(-4).
 

Sample Input
3
3
1 2
2 1
5 1
1
4
3
1 3
2 2
5 1
1
4
3
1 4
2 3
5 1
1
4
 

Sample Output
Case #1:
101.3099324740
Case #2:
90.0000000000
Case #3:
78.6900675260
 
题意：n块木板，q组询问，木板的描述为xi和hi，询问的是位于x时，仰角为多少？
思路：离线处理，将询问点也视为木板，然后类似与求凸包的方法，通过维护向量的“单调性”来保证当前队列的第一个点即为目标点（即仰角的边界）。
用一张图来解释该过程：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;
#define REP(_,a,b) for(int _ = (a); _ <= (b); _++)
const double eps = 1e-10;
const  int maxn = 1e6+10;
const double PI = acos(-1.0);
int n,m;
int len;
double ans[maxn];
struct Point{
    double x,y;
    bool flag;
    int id;
    Point (double x = 0,double y = 0,bool flag = false):x(x),y(y),flag(flag){}

};
typedef Point Vector;
double Cross(Vector A,Vector B) {return A.x*B.y-A.y*B.x;}
double Dot(Vector A,Vector B) {return A.x*B.x+A.y*B.y;}
double Length(Vector A) {return sqrt(Dot(A,A));}
double Angle(Vector A,Vector B) {return acos(Dot(A,B)/Length(A)/Length(B));}
Vector operator + (Vector A,Vector B) {
	return Vector(A.x+B.x,A.y+B.y);
}
Vector operator - (Vector A,Vector B){
	return Vector(A.x-B.x,A.y-B.y);
}
Vector operator * (Vector A,double p){
	return Vector(A.x*p,A.y*p);
}
Vector operator / (Vector A,double p){
	return Vector(A.x/p,A.y/p);
}
int dcmp(double x){
	if(fabs(x) < eps) return 0;
	else return x < 0? -1:1;
}
bool operator < (const Point &a,const Point &b){
	return dcmp(a.x-b.x) <0 || dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)<0;
}

bool operator == (const Point &a,const Point &b){
	return dcmp(a.x-b.x)==0&& dcmp(a.y-b.y)==0;
}
bool cmp1(Point a,Point b) {
    return a.x < b.x;
}
bool cmp2(Point a,Point b) {
    return a.x > b.x;
}
Point P[maxn],ret[maxn];
void input() {
    memset(ans,0,sizeof ans);
    scanf("%d",&n);
    REP(i,0,n-1) {
        scanf("%lf%lf",&P[i].x,&P[i].y);
        P[i].flag = false;
    }
    scanf("%d",&m);
    len = n+m;
    REP(i,0,m-1) {
        double t;
        scanf("%lf",&t);
        P[i+n].x = t;
        P[i+n].y = 0;
        P[i+n].id = i;
        P[i+n].flag = true;
    }
    P[len].flag = false;
    P[len].x = 0;
    P[len++].y = 0;
    P[len].flag = false;
    P[len].x = 1e8;
    P[len++].y = 0;

}
void solve() {
    sort(P,P+len,cmp1);
    int  cur = 0;
    ret[0] = P[0];
    for(int i = 1; i < len; i++) {
        while(cur >= 1 && dcmp(Cross(ret[cur]-ret[cur-1],P[i]-ret[cur])) >= 0) {
            cur--;
        }
        if(P[i].flag) {
            ans[P[i].id] += Angle(P[i]-ret[cur],Vector(0,-1));
        }
        ret[++cur] = P[i];
    }
    sort(P,P+len,cmp2);
    ret[0] = P[0];
    cur = 0;
    for(int i = 1; i < len; i++) {
          while(cur>=1 && dcmp(Cross(ret[cur]-ret[cur-1],P[i]-ret[cur])) <=  0) {
            cur--;
        }
        if(P[i].flag) {
            ans[P[i].id] += Angle(ret[cur]-P[i],Vector(0,1));
        }
        ret[++cur] = P[i];
    }
    for(int i = 0; i  < m; i++) {
        printf("%.6lf\n",ans[i]/PI*180.0);
    }
}
int main(){
    int  ncase,T=1;
    cin >> ncase;
    while(ncase--) {
        input();
        printf("Case #%d:\n",T++);
        solve();
    }
    return 0;
}


HDU 5033 Building(类凸包+向量叉积的应用)


联系
我们