55 分求助
查看原帖
55 分求助
320423
s4CRIF1CbUbbL3AtIAly楼主2024/1/22 14:34

rt。第一个点过了,其它点只有第二问对了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
#define fi first
#define se second
#define endl '\n'
#define mp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define Cl(x) memset(x,0,sizeof(x))
const bool DC=0;
const ll mod=0;
const int N=0;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll qpow(ll a,ll b,ll p=mod){ll ans=1;for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;}
void NO(){cout<<"NO\n";}
void YES(){cout<<"YES\n";}
mt19937 rnd((unsigned long long)new char);
int rnad(){return abs((int)rnd());}
int rd(int l,int r){return rnad()%(r-l+1)+l;}

typedef double db;
struct pos{
	db x,y;int id;
	const pos operator +(const pos b){return {x+b.x,y+b.y};}
	const pos operator -(const pos b){return {x-b.x,y-b.y};}
};
db dis(pos a,pos b){return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
db sq(pos a,pos b){return a.x*b.y-a.y*b.x;}
db tri(pos a,pos b,pos c){return sq(b-a,c-b);}
bool m(pos a,pos b){return (a.y==b.y)?(a.x<b.x):(a.y<b.y);}
pos a[50005];
pos ans[50005];
struct stk{
	int size;
	pos a[50005];
	stk(){size=0;}
	void push(pos x){a[++size]=x;}
	void pop(){size--;}
	pos one(){return a[size];}
	pos two(){return a[size-1];}
}s;

void __INIT__(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
void __SOLVE__(int _case){
	int n,v=0;
	cin>>n;
	for(int i=1;i<=n;i++){
		double m,c;
		cin>>m>>c;
		a[i]={m*c,m,i};
	}
	sort(a+1,a+n+1,m);
	s.push(a[1]);s.push(a[2]);
	for(int i=3;i<=n;i++){
		while(s.size>1&&tri(s.two(),s.one(),a[i])<=0) s.pop();
		s.push(a[i]);
	}
	for(int i=1;i<=s.size-1;i++) ans[++v]=s.a[i];
	s.size=0;
	s.push(a[n]);s.push(a[n-1]);
	for(int i=n-2;i>=1;i--){
		while(s.size>1&&tri(s.two(),s.one(),a[i])<=0) s.pop();
		s.push(a[i]);
	}
	for(int i=1;i<=s.size-1;i++) ans[++v]=s.a[i];
	ans[v+1]=a[1];
	db ANS=0;
	pos x,y;
	if(v==2)ANS=sq(ans[1],ans[2]),x=ans[1],y=ans[2];
	else for(int i=1,j=3;i<=v;i++){
		while(abs(sq(ans[i],ans[j]))<abs(sq(ans[i],ans[j+1])))if(++j>v)j=1;
		if(sq(ans[i],ans[i+1])>ANS)ANS=sq(ans[i],ans[i+1]),x=ans[i],y=ans[i+1];
		if(sq(ans[i],ans[j])>ANS)ANS=sq(ans[i],ans[j]),x=ans[i],y=ans[j];
		if(sq(ans[j],ans[i+1])>ANS)ANS=sq(ans[j],ans[i+1]),x=ans[j],y=ans[i+1];
	}
	cout<<x.id<<" "<<y.id<<"\n"<<v<<"\n";
	for(int i=1;i<=v;i++)cout<<ans[i].id<<" \n"[i==v];
}
int main(){/*freopen(".in","r",stdin);freopen(".out","w",stdout);*/__INIT__();int T;DC?cin>>T,1:T=1;for(int _CASE=1;_CASE<=T;_CASE++)__SOLVE__(_CASE);return 0;}
2024/1/22 14:34
加载中...