QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#461643#784. 旋转卡壳Purslane0 1ms4016kbC++142.2kb2024-07-02 21:12:152024-07-02 21:12:16

Judging History

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

  • [2024-10-16 12:18:36]
  • hack成功,自动添加数据
  • (/hack/1005)
  • [2024-09-24 16:55:39]
  • hack成功,自动添加数据
  • (/hack/888)
  • [2024-07-31 21:52:32]
  • hack成功,自动添加数据
  • (/hack/764)
  • [2024-07-31 21:47:53]
  • hack成功,自动添加数据
  • (/hack/763)
  • [2024-07-02 21:12:16]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4016kb
  • [2024-07-02 21:12:15]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define double long double
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5e5+10;
namespace CALCULATING_GEOMETRY {
	struct Point {int x,y;};
	Point operator +(Point A,Point B) {return {A.x+B.x,A.y+B.y};}
	Point operator -(Point A,Point B) {return {A.x-B.x,A.y-B.y};}
	Point operator *(Point A,int lam) {return {A.x*lam,A.y*lam};}
	double operator *(Point A,Point B) {return A.x*B.y-A.y*B.x;}
	double operator ^(Point A,Point B) {return A.x*B.x+A.y*B.y;}
	bool operator <(Point A,Point B) {if(A.x!=B.x) return A.x<B.x;return A.y<B.y;}
	int tot;Point t[MAXN];
	vector<Point> convex_hull(vector<Point> vc) {
		int n=vc.size();
		sort(vc.begin(),vc.end());
		tot=0; int lst=1;
		ffor(i,0,n-1) {
			if(tot<=lst) t[++tot]=vc[i];
			else {
				while(tot>lst&&(t[tot]-t[tot-1])*(vc[i]-t[tot])<=1e-10) tot--;
				t[++tot]=vc[i];	
			}
		}
		lst=tot;
		roff(i,n-2,0) {
			if(tot<=lst) t[++tot]=vc[i];
			else {
				while(tot>lst&&(t[tot]-t[tot-1])*(vc[i]-t[tot])<=1e-10) tot--;
				t[++tot]=vc[i];	
			}	
		}
		vector<Point> res;
		ffor(i,1,tot-1) res.push_back(t[i]);
		return res;
	}
	struct Line {Point p,d;};
}using namespace CALCULATING_GEOMETRY;
int n; vector<Point> vc;
double p_p_dis(Point A,Point B) {auto calc=A-B;return calc.x*calc.x+calc.y*calc.y;}
double p_l_dis(Point o,Point p1,Point p2) {return abs((o-p1)*(p2-p1));}
int nxt(int u,int n) {return (u+1)%n;}
Point cross(Line A,Line B) {
	double k=((B.p-A.p)*B.d)/(A.d*B.d);
	return A.p+(A.d*k);	
}
#define nxt ((p+1)%vc.size())
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n) {
		int x,y;
		cin>>x>>y,vc.push_back({x,y});	
	}
	vc=convex_hull(vc);
	if(vc.size()==2) return cout<<p_p_dis(vc[0],vc[1]),0;
	int p=0;
	while(p_l_dis(vc[nxt],vc[0],vc[vc.size()-1])>=p_l_dis(vc[p],vc[0],vc[vc.size()-1])) p=nxt;
	double ans=max(p_p_dis(vc[0],vc[p]),p_p_dis(vc[vc.size()-1],vc[p]));
	ffor(i,0,vc.size()-2) {
		if(p_l_dis(vc[nxt],vc[i],vc[i+1])>=p_l_dis(vc[p],vc[i],vc[i+1])) p=nxt;
		ans=max(ans,max(p_p_dis(vc[i],vc[p]),p_p_dis(vc[i+1],vc[p])));
	}
	cout<<fixed<<setprecision(10)<<sqrt(ans);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 10
Accepted
time: 1ms
memory: 4016kb

input:

1000
0 0
-997615 -8573
-1988394 -28911
-2726572 -44296
-3491635 -60392
-4419752 -82814
-5298550 -105946
-5723430 -118453
-6608257 -147267
-7034966 -161982
-7563964 -181682
-8507871 -222865
-9499799 -271846
-10090186 -303547
-10400262 -322989
-10614073 -339725
-11081438 -378596
-11791568 -439127
-127...

output:

274339223.1895613901

result:

ok found '274339223.1895614', expected '274339223.1895614', error '0.0000000'

Test #2:

score: -10
Wrong Answer
time: 1ms
memory: 3944kb

input:

1000
0 0
-887614 -1937
-1459359 -3808
-2421409 -24096
-3273181 -48456
-3917594 -76664
-4402753 -100164
-5375022 -150897
-5993935 -192089
-6587159 -238825
-7549680 -333298
-8330993 -416479
-9244392 -515027
-10010900 -598589
-10374584 -640275
-10767641 -686907
-11173081 -741316
-11821952 -833327
-1260...

output:

262370087.0661462524

result:

wrong answer 1st numbers differ - expected: '262687047.9274906', found: '262370087.0661463', error = '0.0012066'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%