~~震惊!LCT竟比模拟退火更加玄学,这究竟是人性的扭曲还是道德的沦丧~~
by WYXkk @ 2019-03-28 19:02:51
@[咯咯咯](/space/show?uid=87510) ~~毕竟十万个印度女工~~
by GoldenPotato137 @ 2019-03-28 19:04:18
@[咯咯咯](/space/show?uid=87510) 其实应该是你的程序的时间非常接近TLE,然后时间又会有一定程度的浮动,所以有的TLE有的AC,不过如果你是WA我就没什么说的了
by WYXkk @ 2019-03-28 19:08:07
这不是很正常嘛……感觉最慢的评测姬和最快的差了好多的说
by ✡Dustaria✡ @ 2019-03-28 19:08:40
@[WYXkk](/space/show?uid=130151) https://www.luogu.org/recordnew/show/17671645
%%%是这样的
by 咯咯咯 @ 2019-03-28 19:11:19
@[咯咯咯](/space/show?uid=87510)
评测时间与评测机压力成正比。
by Smile_Cindy @ 2019-03-28 19:11:43
还有问下,为啥有的程序在洛谷过不了在其他OJ可以过
by 咯咯咯 @ 2019-03-28 19:13:11
这个程序在LOJ上过了,这里30分
题目:https://www.luogu.org/problemnew/show/P4250
```cpp
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define For(i,a,b) for(int i=a;i<=b;i++)
#define ABS(x) ((x)<0?(-(x)):(x))
const double LIM=1e-7;
const int N=2e5+1000;
const double INF=1e30;
struct DATA
{
double x,y;
DATA operator +(const DATA &other) const{return (DATA){x+other.x,y+other.y};}
DATA operator -(const DATA &other) const{return (DATA){x-other.x,y-other.y};}
DATA operator *(const double &other) const{return (DATA){x*other,y*other};}
DATA operator /(const double &other) const{return (DATA){x/other,y/other};}
bool operator ==(const DATA &other) const{return ABS(x-other.x)<=LIM&&ABS(y-other.y)<=LIM;}
} s[N];
double cross(DATA a,DATA b){return a.x*b.y-b.x*a.y;}
double dot(DATA a,DATA b){return a.x*b.x+a.y*b.y;}
struct LINE
{
DATA st,ed;double ang;int num;
bool operator <(const LINE &other) const
{
DATA temp=other.st-st;
if (ABS(ang-other.ang)<=LIM) return cross(other.st-st,other.ed-st)>0;
else return ang<other.ang;
}
} p[N];
DATA point(LINE a,LINE b)
{
DATA A=a.st,B=a.ed,C=b.st,D=b.ed;
return C+(D-C)*(cross(A-C,B-A)/cross(D-C,B-A));
}
int n;
double ans_S=0,ans_s=0;
std::deque<DATA> Q;
std::deque<LINE> P;
int main()
{
// freopen("convex.in","r",stdin);
// freopen("convex.out","w",stdout);
scanf("%d",&n);
For(i,1,n) scanf("%lf%lf",&s[i].x,&s[i].y);s[n+1]=s[1];
int cnt=0;
For(i,2,n)
{
++cnt;
double A=((s[1].y-s[2].y)-(s[i].y-s[i+1].y)),B=-((s[1].x-s[2].x)-(s[i].x-s[i+1].x)),C=(cross(s[1],s[2])-cross(s[i],s[i+1]));
double k,b;
if (ABS(B)>LIM)
{
k=-A/B;b=-C/B;
p[cnt]=(LINE){(DATA){0,b},(DATA){1,k+b}};
if (-B<0) std::swap(p[cnt].st,p[cnt].ed);
}
else
{
p[cnt]=(LINE){(DATA){-C/A,0},(DATA){-C/A,1}};
if (A<0) std::swap(p[cnt].st,p[cnt].ed);
}
DATA temp=p[cnt].ed-p[cnt].st;
p[cnt].ang=atan2(temp.y,temp.x);
p[cnt].num=cnt;
}
For(i,1,n)
{
++cnt;
p[cnt]=(LINE){s[i],s[i+1]};p[cnt].num=cnt;
DATA temp=p[cnt].ed-p[cnt].st;
p[cnt].ang=atan2(temp.y,temp.x);
}
std::sort(p+1,p+1+cnt);
For(i,1,cnt)
{
if (i>1&&ABS(p[i].ang-p[i-1].ang)<=LIM) continue;
while (Q.size()&&cross(p[i].ed-Q[Q.size()-1],p[i].st-Q[Q.size()-1])>LIM) Q.pop_back() ,P.pop_back() ;
while (Q.size()&&cross(p[i].ed-Q[0],p[i].st-Q[0])>LIM) Q.pop_front() ,P.pop_front() ;
P.push_back(p[i]);
if (P.size()>1) Q.push_back(point(P[P.size()-1],P[P.size()-2]));
}
while (Q.size()&&cross(P[0].ed-Q[Q.size()-1],P[0].st-Q[Q.size()-1])>LIM) Q.pop_back() ,P.pop_back() ;
while (Q.size()&&cross(P[0].ed-Q[0],P[0].st-Q[0])>LIM) Q.pop_front(),P.pop_front();
if (P.size()>1) Q.push_back(point(P[0],P[P.size()-1]));
For(i,1,n) ans_S+=cross(s[i],s[i+1]);
For(i,0,Q.size()-2) ans_s+=cross(Q[i],Q[i+1]);ans_s+=cross(Q[Q.size()-1],Q[0]);
ans_S=ABS(ans_S);
ans_s=ABS(ans_s);
printf("%.4lf\n",ans_s/ans_S);
return 0;
}
```
by 咯咯咯 @ 2019-03-28 19:15:18