题解 P3256 【[JLOI2013]赛车】

2017-09-28 16:15:08


其实这题就是个简单的半平面交。。

强制只能在第一象限

做题的时候突然傻掉了

#include<bits/stdc++.h>
using namespace std;
int n,d,z[1000000];
bool flag[1000000];
struct lsg{int x,y,z;}a[1000000];
bool cmp(lsg x,lsg y){return x.x<y.x||x.x==y.x&&x.y<y.y;}
bool cmp1(int x,int y){return a[x].z<a[y].z;}
double pd1(int x,int y){//两直线交点
        double xx=double(a[x].y-a[y].y)/(a[y].x-a[x].x);
        return xx;
    }
bool pd(int x,int y,int z){//判断y是否完全被x和z覆盖
        double xx=pd1(x,y);
        double yy=pd1(x,z);
        return xx>yy;
    }
int main(){
    ios::sync_with_stdio(false);
    cin>>n;for (int i=1;i<=n;i++)cin>>a[i].y,a[i].z=i;
    for (int i=1;i<=n;i++)cin>>a[i].x;
    sort(a+1,a+1+n,cmp);for (int i=1;i<=n;i++){
        while(d>=1&&pd1(z[d],i)<0)d--;
        while(d>=2&&pd(z[d-1],z[d],i))d--;
        z[++d]=i;
    }sort(z+1,z+1+d,cmp1);cout<<d<<endl;
    for (int i=1;i<=d;i++)cout<<a[z[i]].z<<' ';
}