首页 > 代码库 > bzoj - 1007
bzoj - 1007
1 #include <algorithm> 2 #include <cstring> 3 #include <cstdio> 4 #include <bitset> 5 #include <vector> 6 #include <queue> 7 #include <stack> 8 #include <cmath> 9 #include <list> 10 #include <set> 11 #include <map> 12 #define rep(i,a,b) for(int i = a;i <= b;++ i) 13 #define per(i,a,b) for(int i = a;i >= b;-- i) 14 #define mem(a,b) memset((a),(b),sizeof((a))) 15 #define FIN freopen("in.txt","r",stdin) 16 #define FOUT freopen("out.txt","w",stdout) 17 #define IO ios_base::sync_with_stdio(0),cin.tie(0) 18 #define mid ((l+r)>>1) 19 #define ls (id<<1) 20 #define rs ((id<<1)|1) 21 #define N 50005 22 #define INF 0x3f3f3f3f 23 #define INFF ((1LL<<62)-1) 24 #define mod 998244353 25 typedef long long ll; 26 using namespace std; 27 28 int n,q[N],ans[N]; // q[n] = [l, r); 29 struct Node{ 30 int a,b,id; 31 bool operator < (const Node &r) const { 32 if(a == r.a) return b > r.b; 33 return a < r.a; 34 } 35 }node[N]; 36 double cal(int x, int y){ 37 double ans = (node[y].b-node[x].b)*1.0/(node[x].a-node[y].a); 38 return ans; 39 } 40 int main() 41 {IO; 42 //FIN; 43 while(cin >> n){ 44 rep(i, 1, n) { cin >> node[i].a >> node[i].b; node[i].id = i; } 45 sort(node+1, node+n+1); 46 int top = 0; 47 rep(i, 1, n){ 48 if(top >= 2){ 49 while(top >= 2){ 50 double x = cal(i, q[top-1]), X = cal(q[top-1], q[top-2]); 51 if(x <= X) top--; 52 else 53 break; 54 } 55 } 56 q[top++] = i; 57 } 58 int len = 0; 59 rep(i, 0, top-1) ans[len++] = node[q[i]].id; 60 sort(ans, ans+len); 61 rep(i, 0, len-1) cout << ans[i] << " "; 62 } 63 return 0; 64 }
bzoj - 1007
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。