QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#372915#4368. OilInfinityNS#WA 1ms4128kbC++141.5kb2024-03-31 20:45:362024-03-31 20:45:38

Judging History

你现在查看的是最新测评结果

  • [2024-03-31 20:45:38]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4128kb
  • [2024-03-31 20:45:36]
  • 提交

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'