QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#110977 | #3139. Largest Quadrilateral | acnockm12123 | WA | 2ms | 3652kb | C++20 | 2.2kb | 2023-06-05 04:26:48 | 2023-06-05 04:26:52 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair<int,int> PII;
#define X first
#define Y second
inline int read()
{
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int maxn=2010;
const double eps=1e-8;
struct Point{
double x,y;
Point() {}
Point(double _1,double _2):x(_1),y(_2) {}
Point operator - (const Point&s) const {return Point(x-s.x,y-s.y);}
double operator * (const Point&s) const {return x*s.y-y*s.x;}
double len() {return x*x+y*y;}
}a[maxn],p[maxn];
typedef Point Vec;
double dis(Point a,Point b){
return (a-b).len();
}
double S(Point a,Point b,Point c){
return abs((b-a)*(c-a));
}
bool judgeOnLeft(int p0,int p1,int p2){
double s=(a[p1]-a[p0])*(a[p2]-a[p0]);
return s<0 || (s==0 && dis(a[p1],a[p0])>=dis(a[p2],a[p0]));
}
bool cmp(Point p0,Point p1){
double s=(p0-a[1])*(p1-a[1]);
return s<0 || (s==0 && dis(p0,a[1])>=dis(p1,a[1]));
}
int n,top,sta[maxn];
double ans;
int Graham()
{
int temp=1,m=0;
for(int i=2;i<=n;i++)
if(a[i].x<a[temp].x || (a[i].x==a[temp].x && a[i].y<a[temp].y))temp=i;
swap(a[temp],a[1]);
sort(a+2,a+n+1,cmp);
a[n+1]=a[1];
sta[++top]=1;sta[++top]=2;
for(int i=3;i<=n+1;i++)
{
while(top>1 && judgeOnLeft(sta[top-1],i,sta[top]))top--;
sta[++top]=i;
}
for(int i=1;i<=top;i++)p[m++]=a[sta[i]];//,printf("%lf %lf\n",p[i-1].x,p[i-1].y);
return m-1;
}
double solve()
{
if(n<4)return 0.000;
double ans=0;
for(int i=0;i<n;i++)
{
int k=i+1,l=i+3;
for(int j=i+2;j<n;j++)
{
while(S(p[i],p[j],p[(k+1)%n])-S(p[i],p[j],p[k])>-eps)k=(k+1)%n;
while(S(p[i],p[j],p[(l+1)%n])-S(p[i],p[j],p[l])>-eps)l=(l+1)%n;
ans=max(ans,S(p[i],p[j],p[k])+S(p[i],p[j],p[l]));
// printf("%d %d %d %d\n",i,j,k,l);
}
}
return ans/2.0;
}
int main()
{
n=read();
if(n<3)return puts("0.000"),0;
for(int i=1;i<=n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);
n=Graham();
printf("%.3lf\n",solve());
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 3652kb
input:
3 5 0 0 1 0 3 1 1 2 0 1 4 0 0 4 0 0 4 1 1 4 0 0 1 1 2 2 1 1
output:
0.000
result:
wrong answer 1st lines differ - expected: '3', found: '0.000'