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;
}

Submission Info

Submission Time
Task B - Jumps
User Pajaraja
Language C++14 (GCC 5.4.1)
Score 0
Code Size 928 Byte
Status IE