QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #329164 | #1880. Nikanor Loves Games | Skyjoy | Compile Error | / | / | C++14 | 3.1kb | 2024-02-16 14:20:49 | 2024-02-16 14:20:49 |
Judging History
answer
#include<bits/stdc++.h>
#define I using
#define love namespace
#define Elaina std
#define ll long long
I love Elaina;
const int N=500010;
ll read(){
ll x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
namespace AyaseEli{
struct node{
double x,y;
bool operator<(const node &rhs)const{return (x!=rhs.x)?x<rhs.x:y<rhs.y;}
};
node operator+(node a,node b){return (node){a.x+b.x,a.y+b.y};}
node operator-(node a,node b){return (node){a.x-b.x,a.y-b.y};}
double operator*(node a,node b){return a.x*b.x+b.y*a.y;}
double cross(node a,node b){return a.x*b.y-b.x*a.y;}
double dist(node a,node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
bool cmp(node a,node b){
double tmp=cross(a,b);
if(tmp>0)return 1;
else if(tmp==0&&dist((node){0,0},a)<dist((node){0,0},b))return 1;
else return 0;
}
bool CheckIn(vector<node>&a,node b){
if(cross(b-a[0],a[1]-a[0])>0||cross(a.back()-a[0],b-a[0])>0)return 0;
int l=1,r=a.size()-1,pos=0;
while(l<=r){
int mid=(l+r)/2;
if(cmp(b-a[0],a[mid]-a[0]))r=mid-1,pos=mid-1;
else l=mid+1;
}
return cross(b-a[pos],a[(pos+1)%a.size()]-a[pos])<=0;
}
void ConvexHull(vector<node>a,vector<node>&b){
sort(a.begin(),a.end());
b.clear();
for(int i=0;i<a.size();i++){
while(b.size()>1&&cross(b[b.size()-2]-b.back(),a[i]-b.back())>=0)b.pop_back();
b.push_back(a[i]);
}
int lim=b.size();
for(int i=a.size()-2;i>=0;i--){
while(b.size()>lim&&cross(b[b.size()-2]-b.back(),a[i]-b.back())>=0)b.pop_back();
b.push_back(a[i]);
}
b.pop_back();
}
void Minkowski(vector<node>&a,vector<node>&b,vector<node>&c){
if(a.empty()||b.empty()){
if(a.empty())c=b;
if(b.empty())c=a;
return;
}
c.clear();
int i=0,j=0;
node cur=a[0]+b[0],t1,t2;
c.push_back(cur);
while(i<a.size()&&j<b.size()){
t1=(i<a.size()-1)?a[i+1]-a[i]:a[0]-a[i],t2=(j!=b.size()-1)?b[j+1]-b[j]:b[0]-b[j];
if(cross(t1,t2)>0||(cross(t1,t2)==0&&t1*t2>0))cur=cur+t1,i++;
else cur=cur+t2,j++;
c.push_back(cur);
}
while(i<a.size()){
cur=cur+((i!=a.size()-1)?a[i+1]-a[i]:a[0]-a[i]),i++;
c.push_back(cur);
}
while(j<b.size()){
cur=cur+((j!=b.size()-1)?b[j+1]-b[j]:b[0]-b[j]),j++;
c.push_back(cur);
}
ConvexHull(c,c);
}
}
I love AyaseEli;
ll n,a[N],b[N],x[N],pos[N<<1],sum[N<<1],m;
double ans=-1e18;
vector<node>A;
int main(){
n=read();
for(int i=1;i<=n;i++)a[i]=pos[2*i-1]=read(),b[i]=pos[2*i]=read(),x[i]=read();
pos[2*n+1]=1;
sort(pos+1,pos+2*n+2);
m=unique(pos+1,pos+2*n+2)-pos-1;
for(int i=1;i<=n;i++){
a[i]=lower_bound(pos+1,pos+m+1,a[i])-pos,b[i]=lower_bound(pos+1,pos+m+1,b[i])-pos;
sum[a[i]]+=2*x[i],sum[b[i]]+=2*x[i],sum[0]-=2*x[i];
}
for(int i=1;i<=m;i++){
sum[i]+=sum[i-1];
A.push_back((node){pos[i],sum[i]});
}
ConvexHull(A,A);
for(int i=0,j=A.size()-1;i<A.size();i++){
while(j&&(ll)A[j].y-4ll*A[i].x*A[j].x<=(ll)A[j-1].y-4ll*A[i].x*A[j-1].x)j--;
ans=max(ans,(ll)A[i].y+(ll)A[j].y-(ll)(4ll*A[i].x*A[j].x));
}
printf("%lf",ans/4);
return 0;
}
Details
answer.code: In function ‘int main()’:
answer.code:104:41: warning: narrowing conversion of ‘pos[i]’ from ‘long long int’ to ‘double’ [-Wnarrowing]
104 | A.push_back((node){pos[i],sum[i]});
| ~~~~~^
answer.code:104:48: warning: narrowing conversion of ‘sum[i]’ from ‘long long int’ to ‘double’ [-Wnarrowing]
104 | A.push_back((node){pos[i],sum[i]});
| ~~~~~^
answer.code:109:24: error: no matching function for call to ‘max(double&, long long int)’
109 | ans=max(ans,(ll)A[i].y+(ll)A[j].y-(ll)(4ll*A[i].x*A[j].x));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)’
257 | max(const _Tp& __a, const _Tp& __b)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: template argument deduction/substitution failed:
answer.code:109:24: note: deduced conflicting types for parameter ‘const _Tp’ (‘double’ and ‘long long int’)
109 | ans=max(ans,(ll)A[i].y+(ll)A[j].y-(ll)(4ll*A[i].x*A[j].x));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
303 | max(const _Tp& __a, const _Tp& __b, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: template argument deduction/substitution failed:
answer.code:109:24: note: deduced conflicting types for parameter ‘const _Tp’ (‘double’ and ‘long long int’)
109 | ans=max(ans,(ll)A[i].y+(ll)A[j].y-(ll)(4ll*A[i].x*A[j].x));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)’
5795 | max(initializer_list<_Tp> __l)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: template argument deduction/substitution failed:
answer.code:109:24: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘double’
109 | ans=max(ans,(ll)A[i].y+(ll)A[j].y-(ll)(4ll*A[i].x*A[j].x));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)’
5805 | max(initializer_list<_Tp> __l, _Compare __comp)
| ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: template argument deduction/substitution failed:
answer.code:109:24: note: mismatched types ‘std::initializer_list<_Tp>’ and ‘double’
109 | ans=max(ans,(ll)A[i].y+(ll)A[j].y-(ll)(4ll*A[i].x*A[j].x));
| ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~