这一题WA了好久,对拍才查出来错,因为放入单调栈的时候少考虑了前两种元素(1,10),(2,13)这种case,忘了把第二个放进去。
维护一个单调栈(凸包),两个方向各遍历一次。每次只遍历单调栈,可构成凸包截止。
#include<iostream> #include<stdio.h> #include<cstdio> #include<stdlib.h> #include<vector> #include<string> #include<cstring> #include<cmath> #include<algorithm> #include<stack> #include<queue> #include <ctype.h> using namespace std; int T; int N; int Q; const int maxn=200100; pair<int,int>a[maxn];//first is x,second is h pair<int,int> s[maxn]; int top;//top of stack s,指向下一个代存位置 pair<int,int> l[maxn]; pair<int,int> r[maxn]; int q[maxn];//record the location of query const double pi=acos(-1.0); bool cmp(pair<int,int>a,pair<int,int>b) { return a.first<b.first; } void input() { memset(a,0,sizeof(a)); memset(l,0,sizeof(l)); memset(r,0,sizeof(r)); memset(q,0,sizeof(q)); scanf("%d",&N); for(int i=0;i<N;i++) { scanf("%d %d",&a[i].first,&a[i].second); } scanf("%d",&Q); for(int i=N;i<N+Q;i++) { scanf("%d",&a[i].first); q[i-N]=a[i].first; a[i].second=-(i-N+1);// if<0, then it represent the order of query } sort(a,a+N+Q,cmp); // for(int i=0;i<N+Q;i++) // { // cout<<a[i].first<<" "<<a[i].second<<endl; // } } void convex(int x) { pair<int,int>tmp=s[top]; // cout<<top<<endl; while(top>0) { tmp=s[top-1];//the first element if(tmp.second<a[x].second)//need =? { top--;//to keep descending } else { break; } } // s[top++]=a[x]; while(top>=2)//at least two elements { tmp=s[top-1]; double slope1=1.0*(s[top-2].second-tmp.second)/abs(tmp.first-s[top-2].first); double slope2=1.0*(tmp.second-a[x].second)/abs(a[x].first-tmp.first); if(slope1>=slope2) { top--; } else { s[top++]=a[x]; // cout<<x<<" xx "<<tmp.second<<" "<<a[x].second<<endl; // cout<<x<<" "<<s[top-1].first<<endl; return; } } if(top==1||top==0) { s[top++]=a[x]; // cout<<x<<"xx "<<s[top-1].second<<endl; // cout<<x<<" "<<s[top-1].first<<endl; return; } } void run() { memset(s,0,sizeof(s)); // memset(l,0,sizeof(l)); // memset(r,0,sizeof(r)); top=0; s[top++]=a[0]; for(int i=1;i<N+Q;i++) { //cout<<s[top-1].first<<endl; if(a[i].second>0) { convex(i); } else { while(top>=2) { pair<int,int>tmp=s[top-1]; double slope1=1.0*(s[top-2].second-tmp.second)/abs(tmp.first-s[top-2].first); double slope2=1.0*tmp.second/abs(a[i].first-tmp.first); // cout<<slope1<<" "<<slope2<<endl; if(slope1>=slope2) { top--; } else { break; } } int qry=-a[i].second-1; l[qry]=s[top-1]; // cout<<l[qry].first<<endl;; } } memset(s,0,sizeof(s));//from right end // cout<<"right"<<endl; top=0; s[top++]=a[N+Q-1]; for(int i=N+Q-2;i>=0;i--) { if(a[i].second>0) { convex(i); //cout<<s[top-1].first<<endl; } else { while(top>=2) { pair<int,int>tmp=s[top-1]; double slope1=1.0*(s[top-2].second-tmp.second)/abs(tmp.first-s[top-2].first); double slope2=1.0*tmp.second/abs(a[i].first-tmp.first); // cout<<tmp.first<<" tmp "<<tmp.second<<endl; if(slope1>=slope2) { top--; } else { break; } } int qry=-a[i].second-1; r[qry]=s[top-1]; // cout<<top-1<<" "<<qry<<" "<<r[qry].first<<endl; } } } double cal(int x) { // cout<<x<<" "<<l[x].second<<" "<<q[x]<<" "<<l[x].first<<endl; // cout<<x<<" "<<r[x].second<<" "<<q[x]<<" "<<r[x].first<<endl; double theta1=atan2(l[x].second,(q[x]-l[x].first)); double theta2=atan2(r[x].second,(r[x].first-q[x])); return (pi-theta1-theta2)/pi*180.0; } int main() { // freopen("input.txt","r",stdin); freopen("data.txt","r",stdin); // freopen("out1.txt","w",stdout); scanf("%d",&T); for(int ca=1;ca<=T;ca++) { input(); run(); printf("Case #%d:\n",ca); for(int i=0;i<Q;i++) { printf("%.10lf\n",cal(i)); } } return 0; }