QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#546122 | #784. 旋转卡壳 | qinglu09 | 0 | 0ms | 0kb | C++14 | 4.3kb | 2024-09-03 20:00:44 | 2024-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: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%