#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
typedef long double ll;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
pair<ll,ll> it[2001];
llo cc[2001];
/*ll sl(llo aa,llo bb){
return (it[aa].b-it[bb].b)/(it[aa].a-it[bb].a);
}*/
ll dist2(llo i,llo j){
return (it[i].a-it[j].a)*(it[i].a-it[j].a)+(it[i].b-it[j].b)*(it[i].b-it[j].b);
}
/*ll sect(pair<ll,ll> aa,pair<ll,ll> bb,pair<ll,ll> cc,pair<ll,ll> dd){
}
*/
ll dist(llo k,llo i,llo j){
//ll xx=(dist2(i,k)*dist2(i,k)-dist2(j,k)*dist2(j,k)+dist2(i,j)*dist2(i,j))/((ll)2*dist2(i,j));
ll xx=(dist2(i,k)-dist2(j,k)+dist2(i,j))/((ll)2*sqrt(dist2(i,j)));
///((ll)2*dist2(i,j));
// cout<<dist2(i,k)<<","<<dist2(j,k)<<","<<dist2(i,j)<<"<"<<xx<<endl;
return dist2(i,k)-xx*xx;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
llo n;
cin>>n;
llo ans=0;
for(llo i=0;i<n;i++){
cin>>it[i].a>>it[i].b;
cin>>cc[i];
ans=max(ans,cc[i]);
}
for(llo i=0;i<n;i++){
for(llo j=0;j<n;j++){
if(j==i){
continue;
}
vector<pair<ll,llo>> aa;
vector<pair<ll,llo>> bb;
// cout<<i<<","<<j<<endl;
for(llo k=0;k<n;k++){
if(k==i or k==j){
continue;
}
pair<ll,ll> v1;
pair<ll,ll> v2;
v1={it[j].a-it[i].a,it[j].b-it[i].b};
v2={it[j].a-it[k].a,it[j].b-it[k].b};
if(v1.a*v2.b-v2.b*v2.a>(ll)0){
aa.pb({dist(k,i,j),cc[k]});
// cout<<dist(k,i,j)<<"::"<<k<<endl;
}
else{
bb.pb({dist(k,i,j),cc[k]});
}
}
sort(aa.begin(),aa.end());
sort(bb.begin(),bb.end());
llo cost=cc[i]+cc[j];
ans=max(ans,cost);
for(auto jj:aa){
cost+=jj.b;
ans=max(ans,cost);
}
cost=cc[i]+cc[j];
ans=max(ans,cost);
for(auto jj:bb){
cost+=jj.b;
ans=max(ans,cost);
}
}
}
cout<<ans<<endl;
/*it[10]={0,0};
it[11]={3,0};
it[12]={1.5,2};*/
//cout<<dist(12,10,11)<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
113 ms |
384 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
95 ms |
516 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
