QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#110977#3139. Largest Quadrilateralacnockm12123WA 2ms3652kbC++202.2kb2023-06-05 04:26:482023-06-05 04:26:52

Judging History

This is the latest submission verdict.

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-05 04:26:52]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 3652kb
  • [2023-06-05 04:26:48]
  • Submitted

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());
}


詳細信息

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'