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