QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#335793#2. Boatucup-team0520 1ms4232kbC++233.8kb2024-02-23 23:13:322024-02-23 23:13:32

Judging History

你现在查看的是最新测评结果

  • [2024-02-23 23:13:32]
  • 评测
  • 测评结果:0
  • 用时:1ms
  • 内存:4232kb
  • [2024-02-23 23:13:32]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define eb emplace_back
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define mod 998244353
#define ll long long
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
inline int read()
{
	char ch=getchar(); int nega=1; while(!isdigit(ch)) {if(ch=='-') nega=-1; ch=getchar();}
	int ans=0; while(isdigit(ch)) {ans=ans*10+ch-48;ch=getchar();}
	if(nega==-1) return -ans;
	return ans;
}
void print(vector<int> x){for(int i=0;i<(int)x.size();i++) printf("%d%c",x[i]," \n"[i==(int)x.size()-1]);}
const double eps=1e-11;
int sgn(double x)
{
	if(x<-eps) return -1;
	else if(x>eps) return 1;
	else return 0;
}
struct Vec
{
	double x,y;
	Vec(double a=0,double b=0) {x=a,y=b;}
	double norm() {return x*x+y*y;}
	double abs() {return sqrt(x*x+y*y);}
};
Vec rdvec()
{
	double x,y;
	scanf("%lf %lf",&x,&y);
	return Vec(x,y);
}
Vec operator + (const Vec &x,const Vec &y) {return Vec(x.x+y.x,x.y+y.y);}
Vec operator - (const Vec &x,const Vec &y) {return Vec(x.x-y.x,x.y-y.y);}
Vec operator * (const Vec &x,const double y) {return Vec(x.x*y,x.y*y);}
Vec operator / (const Vec &x,const double y) {return Vec(x.x/y,x.y/y);}
double dis(const Vec &x,const Vec &y) {return (x-y).abs();}
void print(Vec x) {printf("%.10lf %.10lf\n",x.x,x.y);}
double cdot(const Vec &x,const Vec &y) {return x.x*y.x+x.y*y.y;}
double cross(const Vec &x,const Vec &y) {return x.x*y.y-x.y*y.x;}
int ccw(Vec x,Vec y,Vec z)
{
	int w=sgn(cross(y-x,z-x));
	if(w==1) return 1; // ccw
	else if(w==-1) return -1; // cw;
	else return 0; // coline
}
struct Seg
{
	Vec s,t; // two points
	Seg(Vec x,Vec y) {s=x,t=y;}
	Seg() {}
	Vec d() {return t-s;}
	Vec point(double p) {return s+(t-s)*p;}
};
int parallel(Seg p,Seg q) {return sgn(cross(p.d(),q.d()))==0;}
Vec proj(Seg l,Vec x)
{
	double p=cdot(l.t-l.s,x-l.s)/(l.t-l.s).norm();
	return l.point(p);
}
int isintersect(Seg p,Seg q)
{
	if(max(p.s.x,p.t.x)<min(q.s.x,q.t.x)) return 0;
	if(max(q.s.x,q.t.x)<min(p.s.x,p.t.x)) return 0;
	if(max(p.s.y,p.t.y)<min(q.s.y,q.t.y)) return 0;
	if(max(q.s.y,q.t.y)<min(p.s.y,p.t.y)) return 0;
	if(ccw(q.s,p.s,p.t)*ccw(q.t,p.s,p.t)==1) return 0;
	if(ccw(p.s,q.s,q.t)*ccw(p.t,q.s,q.t)==1) return 0;
	return 1;
}
Vec crosspoint(Seg p,Seg q)
{
	double A=cross(p.t-p.s,q.t-q.s);
	double B=cross(p.t-p.s,p.t-q.s);
	return q.s+(q.t-q.s)*(B/A);
}
vector<Vec> halfPlane(vector<Seg> v) // left halfplanes
{
	sort(v.begin(),v.end(),[&](Seg x,Seg y){
		double ang1=atan2(x.d().y,x.d().x);
		double ang2=atan2(y.d().y,y.d().x);
		if(sgn(ang1-ang2)) return ang1<ang2;
		else return ccw(x.s,y.s,y.t)==1;
	});
	auto onRight=[&](Seg s,Vec x) {return ccw(s.s,x,s.t)>=0;};
	static Seg q[1005];
	static Vec p[1005];
	int l=0,r=0; q[0]=v[0];
	for(int i=1;i<(int)v.size();i++)
	{
		while(l<r&&onRight(v[i],p[r])) r--;
		while(l<r&&onRight(v[i],p[l+1])) l++;
		q[++r]=v[i];
		if(parallel(q[r],q[r-1]))
		{
			if(onRight(q[r],q[r-1].s)&&cdot(q[r].d(),q[r-1].d())<eps) return {};
			r--;
			if(!onRight(q[r],v[i].s)) q[r]=v[i];
		}
		if(l<r) p[r]=crosspoint(q[r],q[r-1]);
	}
	while(l<r&&onRight(q[l],p[r])) r--;
	if(r-l<=1) return {};
	p[l]=crosspoint(q[l],q[r]);
	return vector<Vec>(p+l,p+r+1);
}
double Area(vector<Vec> v) // ccw
{
	double ans=0;
	for(int i=1;i+1<(int)v.size();i++) ans+=cross(v[i]-v[0],v[i+1]-v[0]);
	return ans/2;
}
signed main()
{
	int n=read();
	vector<Seg> a;
	Vec v0(0,0),v1(10000,0),v2(10000,10000),v3(0,10000);
	a.emplace_back(v0,v1),a.emplace_back(v1,v2),a.emplace_back(v2,v3),a.emplace_back(v3,v0);
	for(int i=1;i<=n;i++)
	{
		Vec s=rdvec(),t=rdvec();
		a.emplace_back(s,t);
	}
	vector<Vec> ans=halfPlane(a);
	if(ans.empty()) printf("0.0\n");
	else printf("%.1lf\n",Area(ans));
	return 0;
}



Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 4180kb

input:

500
308810287 308810287
53564892 53564892
316377768 316377768
420249597 420249597
731165653 731165653
319087025 319087025
153776963 153776963
425464316 425464316
651047701 651047701
142502072 142502072
31632388 31632388
572337890 572337890
400220429 400220429
414382974 414382974
279400752 279400752
...

output:

0.0

result:

wrong answer 1st lines differ - expected: '553232367', found: '0.0'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Wrong Answer

Test #41:

score: 0
Wrong Answer
time: 1ms
memory: 4232kb

input:

100
191358459 947004691
342443850 366915813
22574423 36448174
228846908 747282766
190110113 253913299
93029730 879223713
290883541 747723417
162887369 973643964
586349400 863191444
242642824 878391136
18343882 502405347
18658435 174450786
308510413 787915209
79222154 665119810
422422946 793255277
53...

output:

0.0

result:

wrong answer 1st lines differ - expected: '167281196', found: '0.0'

Subtask #4:

score: 0
Skipped

Dependency #1:

0%