Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- // CCO '16 P2 - Splitting Hares
- #define EPS 1e-7
- using namespace std;
- int x[4005],y[4005],w[4005];
- vector<int> l,r;
- int cur;
- inline double slope(int i1,int i2) {
- return ((double) (y[i1] - y[i2])) / (x[i1] - x[i2]);
- }
- bool cmp(int i1,int i2) {
- return slope(i1,cur) < slope(i2,cur);
- }
- inline bool eq(double d1,double d2) {
- return (abs(d1 - d2) < EPS);
- }
- int main() {
- int N,i,j,k,sum1,sum2,ans,dec1,dec2,temp;
- double nxt;
- scanf("%d",&N);
- for (i = 0;i < N;i++)
- scanf("%d%d%d",&x[i],&y[i],&w[i]);
- ans = 0;
- for (i = 0;i < N;i++) {
- sum1 = 0;
- sum2 = 0;
- dec1 = 0;
- dec2 = 0;
- l.clear();
- r.clear();
- for (j = 0;j < N;j++) {
- if (x[j] == x[i]) {
- sum1 += w[j];
- sum2 += w[j];
- if (y[j] > y[i])
- dec1 += w[j];
- else if (y[j] < y[i])
- dec2 += w[j];
- }
- else if (x[j] > x[i]) {
- r.push_back(j);
- sum2 += w[j];
- }
- else {
- l.push_back(j);
- sum1 += w[j];
- }
- }
- cur = i;
- sort(l.begin(),l.end(),cmp);
- sort(r.begin(),r.end(),cmp);
- j = 0;
- k = 0;
- while (j < l.size() || k < r.size()) {
- temp = max(max(dec1,dec2) + max(w[i],0),dec1 + dec2 + w[i]);
- ans = max(ans,max(temp,0) + max(sum1,sum2) - dec1 - dec2 - w[i]);
- if (j == l.size())
- nxt = slope(r[k],i);
- else if (k == r.size())
- nxt = slope(l[j],i);
- else
- nxt = min(slope(l[j],i),slope(r[k],i));
- sum1 -= dec1;
- sum2 -= dec2;
- dec1 = 0;
- dec2 = 0;
- while (j < l.size() && eq(slope(l[j],i),nxt)) {
- sum2 += w[l[j]];
- dec1 += w[l[j]];
- j++;
- }
- while (k < r.size() && eq(slope(r[k],i),nxt)) {
- sum1 += w[r[k]];
- dec2 += w[r[k]];
- k++;
- }
- }
- }
- printf("%d\n",ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement