Submission #5382650
Source Code Expand
#include <bits/stdc++.h> #define MAXN 100007 using namespace std; struct tacka{long long x,y; int ind;}; bool cmp(tacka a,tacka b) { if(a.x<b.x) return true; if(a.x>b.x) return false; return a.y>b.y; } tacka a[MAXN]; bool sn[MAXN]; int main() { int n; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].x>>a[i].y; a[i].ind=i; } sort(a+1,a+1+n,cmp); stack<int> st; st.push(1); bool prp=true; for(int i=3;i<=n;i++) if((a[i].x-a[i-1].x)*(a[i-1].y-a[i-2].y)!=(a[i].y-a[i-1].y)*(a[i-1].x-a[i-2].x)) prp=false; if(prp) {cout<<0; return 0;} for(int i=2;i<=n;i++) { while(st.size()>1) { int x=st.top(); st.pop(); int y=st.top(); if((a[i].x-a[x].x)*(a[x].y-a[y].y)>=(a[i].y-a[x].y)*(a[x].x-a[y].x)) {st.push(x); break;} } st.push(i); } while(!st.empty()) {cout<<a[st.top()].ind<<endl; sn[st.top()]=true; st.pop();} for(int i=1;i<=n;i++) if(!sn[i]) cout<<a[i].ind<<endl; }