QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#372915 | #4368. Oil | InfinityNS# | WA | 1ms | 4128kb | C++14 | 1.5kb | 2024-03-31 20:45:36 | 2024-03-31 20:45:38 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
struct pt{
ll x,y;
pt():x(0),y(0){}
pt(ll a,ll b):x(a),y(b){}
};
pt operator - (pt a,pt b){return pt(a.x-b.x,a.y-b.y);}
ll cross(pt a,pt b){return a.x*b.y-a.y*b.x;}
bool collinear(pt a,pt b,pt c){return cross(a-b,c-b)==0;}
int part(pt a){return a.y<0 || (a.y==0 && a.x<0);}
bool operator < (pt a,pt b){return mp(part(a),(ll)0)<mp(part(b),cross(a,b));}
pt Fix(pt a){
if(part(a)==1)return pt(0,0)-a;
return a;
}
const int N=2050;
pt A[N],B[N];
bool was[N];
int val[N];
int main(){
int n;
scanf("%i",&n);
vector<pair<pt,int>> start;
for(int i=1;i<=n;i++){
int x0,x1,y;
scanf("%i %i %i",&x0,&x1,&y);
A[i]=pt(x0,y);
B[i]=pt(x1,y);
val[i]=abs(x1-x0);
start.pb({A[i],val[i]});
start.pb({B[i],val[i]});
}
ll ans=0;
for(auto p:start){
pt C=p.first;
vector<pair<pt,int>> evs;
ll cnt=p.second;
for(int i=1;i<=n;i++){
if(collinear(C,A[i],B[i]))continue;
evs.pb({Fix(A[i]-C),i});
evs.pb({Fix(B[i]-C),i});
}
sort(evs.begin(),evs.end());
for(int i=0,j;i<evs.size();i=j){
for(j=i;j<evs.size() && cross(evs[i].first,evs[j].first)==0;j++){
if(!was[evs[j].second]){
cnt+=val[evs[j].second];
}
}
ans=max(ans,cnt);
for(j=i;j<evs.size() && cross(evs[i].first,evs[j].first)==0;j++){
if(was[evs[j].second]){
cnt-=val[evs[j].second];
}
was[evs[j].second]^=1;
}
}
}
printf("%lld\n",ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3856kb
input:
5 100 180 20 30 60 30 70 110 40 10 40 50 0 80 70
output:
200
result:
ok single line: '200'
Test #2:
score: 0
Accepted
time: 1ms
memory: 4128kb
input:
3 50 60 10 -42 -42 20 25 0 10
output:
25
result:
ok single line: '25'
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 3768kb
input:
1 -100 180 20
output:
0
result:
wrong answer 1st lines differ - expected: '280', found: '0'