既见君子

同济医学生的起落落落落人生记录

BZOJ 3190 赛车

http://www.lydsy.com/JudgeOnline/problem.php?id=3190

题目大意:

求一些y=Ax+B围成的半平面交上的到底用了哪些方程,A,B>=0

感受:

1.咦这是半平面交裸题快写!然后就WA了6个点而且难以拯救

2.百般无奈之下写了一发单调栈,居然过了。

启示:

抓住题目性质,这些方程易于求交点而且相当于一个凸包的四分之一凸壳且又都是整数所以较好处理。

//说辣么多并没有啥卵用,半平面交还是没能A题嘤嘤,我的半平面交怎么办QAQ

code:#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<vector>
#include<cmath>
using namespace std;
const int maxn=200000+5;
#define eps 1e-7
int id[maxn];
int sgn(double v){if(fabs(v)<eps) return 0;return v>0?1:-1;}
struct node{
        int A,B,id;
        bool operator <(const node &c)const{
                if(A==c.A) return B>c.B;
                return A<c.A;
        }
        bool operator ==(const node &c)const{
                return A==c.A&&B==c.B;
        }
}p[maxn],sta[maxn];
int top;
vector <int> G[maxn];
bool isout(node a,node b,node c){
        double deA=b.A-c.A;
        double deB=c.B-b.B;
        double x=deB/deA;
        double y=b.A*x+b.B;
        return sgn(x*a.A-y+a.B)>0;
}
void po(node &c){
        while((top>1&&isout(c,sta[top],sta[top-1]))||top>=1&&c.B>sta[top].B) top--;
        sta[++top]=c;
}
int main(){
        freopen("3190.in","r",stdin);
        freopen("3190.out","w",stdout);
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",&p[i].B),p[i].id=i;
        for(int i=1;i<=n;++i) scanf("%d",&p[i].A);
        sort(p+1,p+n+1);
        int len=1;
        for(int i=2;i<=n;++i) 
                if(p[i].A!=p[len].A) p[++len]=p[i];
                else if(p[i].B==p[len].B){
                        G[p[len].id].push_back(p[i].id);
                }
        for(int i=1;i<=len;++i) 
                po(p[i])/*, printf("%d\n", top)*/;
        for(int i=1;i<=top;++i){
                id[++id[0]]=sta[i].id;
                for(int j=0;j<G[sta[i].id].size();++j) id[++id[0]]=G[sta[i].id][j];
        }
        sort(id+1,id+id[0]+1);
        printf("%d\n",id[0]);
        for(int i=1;i<id[0];++i) printf("%d ",id[i]);
        if(id[0]) printf("%d\n",id[id[0]]);
        return 0;
}


评论
热度(5)
©既见君子
Powered by LOFTER