QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#546122#784. 旋转卡壳qinglu090 0ms0kbC++144.3kb2024-09-03 20:00:442024-09-03 20:00:49

Judging History

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

  • [2024-10-16 12:18:36]
  • hack成功,自动添加数据
  • (/hack/1005)
  • [2024-09-24 16:55:39]
  • hack成功,自动添加数据
  • (/hack/888)
  • [2024-09-03 20:00:49]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-09-03 20:00:44]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define endl '\n'
#define debug(x) cout<<#x<<": "<<x<<endl
#define lowbit(x) (x&-x)
#define gcd __gcd
#define i128 __int128
#define rep(i, a, b) for(ll i = (a); i <= (b); i++)
#define per(i, a, b) for(ll i = (a); i >= (b); i--)
const int N=2e5+10,M=1e3+10;
const ll mod=1e9+7;
const ld eps=1e-12;
const double pi = acos(-1.0);
const double pi1=pi/180,pi2=180/pi;
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
//unordered_map<int,int>mp;
#define poly vector<int>

double dtopi(double x) {return x*pi1;}
double pitod(double x) {return x*pi2;}
int sgn(double x) 
{
    if(fabs(x)<eps) return 0;	//x==0, 精度范围内的近似相等
    return x>0?1:-1;			//返回正负
}

typedef struct point 
{
    double x,y;
    point(double x = 0, double y = 0) : x(x), y(y) {}
    double operator * (point b) {return x*b.x+y*b.y;}//点积
	double operator ^ (point b) {return x*b.y-y*b.x;}//差积
	point operator + (point b) {return point(x+b.x,y+b.y);}
	point operator - (point b) {return point(x-b.x,y-b.y);}
	bool operator == (point b) {return sgn(x-b.x)==0&&sgn(y-b.y)==0;}
	bool operator < (point b) {return sgn(x-b.x)==0?sgn(y-b.y)<0:b.x;}
	bool operator > (point b) {return !(*this<b);}
	point operator * (double k) {return point(k*x,k*y);}//数乘
	point operator / (double k) {return point(x/k,y/k);}//数除
	point trunc(double r) {double l=len();r/=l;return point(x*r,y*r);}//变模长为r
	double len() {return hypot(x,y);}//模长
	double len2() {return x*x+y*y;}//模长平方
	double dis(point b){return hypot(x-b.x,y-b.y);}
}Vector;

double len(Vector a) {return sqrt(a*a);}//模长
Vector norm(Vector a) {return a/len(a);}//单位向量
double dis(point a,point b) {return len(a-b);}
double cross(point a,point b,point c) {return (b-a)^(c-a);} //ab叉乘ac

typedef struct line
{
	point s,e;
	line(){}
	line(point _s,point _e) {s =_s; e= _e;}
	line(point p,double angle)//点斜
	{
		s=p;
		if(sgn(angle-pi/2)==0)  e=(s+point(0,1));
		else e=(s+point(1,tan(angle)));
	}
	line(double a,double b,double c)//ax+by+c=0;
	{
		if(sgn(a)==0) {s=point(0,-c/b);e=point(1,-c/b);}
		else if(sgn(b)==0) {s=point(-c/a,0);e=point(-c/a,1);}
		else {s=point(0,-c/b);e=point(1,(-c-a)/b);}
	}
	double length() {return s.dis(e);}//线段长度
	double angle()//返回[0,π]的基于x轴的斜倾角(弧度制)
	{
		double k=atan2(e.y-s.y,e.x-s.x);
		if(sgn(k)<0) k+=pi;
		if(sgn(k-pi)==0) k-=pi;
		return k;
	}
}seg;


struct polygon
{
	int n=0;
	vector<point>p;
	vector<line>l;
	void add(point x){p.push_back(x),n++;}
	void getline()
	{
		for(int i=0;i<n;i++) 
			l[i]=line(p[i],p[(i+1)%n]);
	}
	struct cmp
	{
		bool operator()(point a,point b) const
		{
			point o={0,0};
			if(cross(o,a,b)==0) return a.x<b.x;
			else return cross(o,a,b)>0;
		}
	};
	void norm() {sort(p.begin(),p.end(),cmp());}//极角排序

	void Andrew()//求凸包
	{
		vector<point>s;
		sort(p.begin(),p.end());
		for(int i=0;i<n;i++)
		{
			while(s.size()>1&&cross(s[s.size()-2],s[s.size()-1],p[i])<=0) s.pop_back();
			s.push_back(p[i]);
		}
		int t=s.size();
		for(int i=n-2;i>=0;i--)
		{
			while(s.size()>t&&cross(s[s.size()-2],s[s.size()-1],p[i])<=0) s.pop_back();
			s.push_back(p[i]);
		}
		if(s.size()>1) s.pop_back();
		p=s,n=s.size();
	}

	double rotating_calipers()//求直径(需要先求凸包)
	{
  		double res=0;
		if(n==1) return 0;
        p.push_back(p[0]);
  		for(int i=0,j=1;i<n;i++)
		{
    		while(cross(p[i],p[i+1],p[j])<cross(p[i],p[i+1],p[(j+1)%n])) j=(j+1)%n;
    		res=max(res,max(dis(p[i],p[j]),dis(p[i],p[j])));
  		}
        p.pop_back();
  		return res;
	}

	double getcircumference()
	{
		double sum=0;
		for(int i=0;i<n;i++) sum+=dis(p[i],p[(i+1)%n]);
		return sum;
	}
};

void solve()
{
	int n;
    cin>>n;
    polygon A;
    for(int i=1;i<=n;i++)
    {
        ll x,y;
        cin>>x>>y;
        A.add(point(x,y));
    }
    A.Andrew();
   cout<<fixed<<setprecision(7)<<A.rotating_calipers();
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	int T=1;
	//cin>>T;

	while(T--)
	{

		solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Runtime Error

Test #1:

score: 0
Runtime Error

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:


result:


Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%