求调
查看原帖
求调
906057
ELECTRODE_kaf楼主2024/11/27 21:41

WA 6060 pts,做法和第二篇题解一致

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define rep(i,x,y) for(ll i=(x);i<=(y);i++)
#define rep_(i,x,y) for(ll i=(x);i>=(y);i--)
#define srt short
#define fi first
#define se second
#define endl putchar('\n')
#define elif else if
#define fin freopen("in.txt","r",stdin)
#define fout freopen("out.txt","w",stdout)
#define count(x) while((x)--)
#define pll pair<ll,ll>
#define IL inline
#define pii pair<int,int>
#define ctn continue
#define sync_off ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define update(x,y,z) x=z(x,(y))
#define reset bool operator
#define mine cout<<"mine\n";
#define pause system("pause")
#define pqueue(x,y) priority_queue<(x),vector<(x)>,y<(x)> >
#define pb push_back
#define db double
#define rout(x,y) cout<<fixed<<setprecision(x)<<(y)
#define xfront(x,y) x=y.front();y.pop()
#define xtop(x,y) x=y.top();y.pop()
#define myclear(qu) while(qu.empty()==0) qu.pop()

const ll N=3000;
ll n;

struct square {
	pll p;
	ll w;
	bool vis;
	db s1,s2;
} a[N];

bool cmp(square x,square y) {
	if(min(x.p.fi,x.p.se)!=min(y.p.fi,y.p.se)) return min(x.p.fi,x.p.se)<min(y.p.fi,y.p.se);
	else return max(x.p.fi,x.p.se)<max(y.p.fi,y.p.se);
}

db cal(pll p) {
	return db(p.se)/db(p.fi);
}

int main() {
	cin>>n;

	rep(i,1,n) {
		cin>>a[i].p.fi>>a[i].p.se>>a[i].w;
		a[i].vis=1;
	}

	sort(a+1,a+n+1,cmp);

//	rep(i,1,n) cout<<a[i].p.fi<<' '<<a[i].p.se<<'\n';
//
//	endl;
	ll ans=0;
	
	rep(i,1,n){
		pll lu= {a[i].p.fi,a[i].p.se+a[i].w},rd= {a[i].p.fi+a[i].w,a[i].p.se};
		db mins=cal(rd),maxs=cal(lu);
		a[i].s1=mins;
		a[i].s2=maxs;
	}
	
	rep(i,1,n) {
		if(a[i].vis) {
//			cout<<"visiting "<<i<<'\n';
			ans++;
//			cout<<"left up:("<<lu.fi<<','<<lu.se<<")\n";
//			pause;


			rep(j,1,i-1) {
				if(a[i].s1<=a[j].s2 and a[i].s1>=a[j].s1 
				or a[i].s2<=a[j].s2 and a[i].s2>=a[j].s1) {
					update(a[i].s1,a[j].s1,min);
					update(a[i].s2,a[j].s2,max);
				}
			}

//			cout<<"mins="<<mins<<'\n';
//			pause;

			rep(j,i+1,n) {
				if(a[j].s1>=a[i].s1 and a[j].s1<=a[i].s2 
				and a[j].s2>=a[i].s1 and a[j].s2<=a[i].s2) {
//					cout<<"find hidden "<<j<<'\n';
					a[j].vis=0;
//					cout<<"mins="<<mins<<"\nmaxs="<<maxs<<"\ns1="<<s1<<"\ns2="<<s2<<'\n';
//					pause;
				}
			}
		}
	}

	cout<<ans;
}
2024/11/27 21:41
加载中...