QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#241321#7680. Subwayucup-team987#RE 1ms3588kbC++206.4kb2023-11-06 02:16:362023-11-06 02:16:36

Judging History

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

  • [2023-11-06 02:16:36]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3588kb
  • [2023-11-06 02:16:36]
  • 提交

answer

#include<iostream>
#include<cassert>
using namespace std;
#include<iostream>
#include<algorithm>
#include<vector>
using Int=long long;
int sign(Int a){return a>0?1:a<0?-1:0;}
Int sqr(Int a){return a*a;}
struct Rational{
	Int a,b;
	Rational(Int a_=0):a(a_),b(1){}
	Rational(Int a_,Int b_){
		Int g=a_,h=b_;
		while(h){
			Int t=g%h;
			g=h;
			h=t;
		}
		a=a_/g;
		b=b_/g;
		if(b<0)a=-a,b=-b;
	}
	bool operator<(const Rational&r)const{return a*r.b<r.a*b;}
	bool operator==(const Rational&r)const{return a==r.a&&b==r.b;}
};
struct Point{
	Int x,y;
	Point(Int x_=0,Int y_=0):x(x_),y(y_){}
	Point operator-()const{return Point(-x,-y);}
	Point operator+(const Point&p)const{return Point(x+p.x,y+p.y);}
	Point operator-(const Point&p)const{return Point(x-p.x,y-p.y);}
	Point operator*(const Int k)const{return Point(x*k,y*k);}
	bool operator<(const Point&p)const{return x==p.x?y<p.y:x<p.x;}
	bool operator==(const Point&p)const{return x==p.x&&y==p.y;}
};
istream&operator>>(istream&is,Point&p){return is>>p.x>>p.y;}
ostream&operator<<(ostream&os,const Point&p){return os<<p.x<<' '<<p.y;}
struct Line{
	Point p1,p2;
	Line(Point p1_=Point(),Point p2_=Point()):p1(p1_),p2(p2_){}
};
struct Segment:Line{
	Segment(Point p1_=Point(),Point p2_=Point()):Line(p1_,p2_){}
};
struct Circle{
	Point o;
	Int r;
	Circle(Point o_=Point(),Int r_=0):o(o_),r(r_){}
};
using Polygon=vector<Point>;
//function list begin
Point vec(const Line&);
Int norm(const Point&);
Int norm(const Line&);
int argtype(const Point&);//(-pi,0]->-1,(0,pi]->1,(0,0)->0
bool argless(const Point&,const Point&);//sorting points with arg
Int dot(const Point&,const Point&);
Int cross(const Point&,const Point&);
enum{ONLINE_FRONT=-2,CLOCKWISE=-1,ON_SEGMENT=0,COUNTER_CLOCKWISE=1,ONLINE_BACK=2};
int ccw(const Point&,const Point&);
int ccw(const Point&,const Point&,const Point&);
int ccw(const Line&,const Point&);
bool orthogonal(const Point&,const Point&);
bool orthogonal(const Line&,const Line&);
bool parallel(const Point&,const Point&);
bool parallel(const Line&,const Line&);
bool intersect(const Line&,const Point&);
bool intersect(const Line&,const Line&);
bool intersect(const Segment&,const Point&);
bool intersect(const Segment&,const Segment&);
bool intersect(const Line&,const Segment&);
bool intersect(const Segment&,const Line&);
bool intersect(const Circle&,const Point&);
int intersect(const Circle&,const Line&);//overflow, count contacts
int intersect(const Circle&,const Segment&);//overflow, count contacts
bool intersect(const Circle&,const Circle&);
int count_tangent(const Circle&,const Circle&);//count common tangents
Int distance2(const Point&,const Point&);
Rational distance2(const Line&,const Point&);
Rational distance2(const Line&,const Line&);
Rational distance2(const Segment&,const Point&);
Rational distance2(const Segment&,const Segment&);
Rational distance2(const Line&,const Segment&);
Rational distance2(const Segment&,const Line&);
bool is_convex(const Polygon&);
Polygon convex_hull(Polygon,bool=false);
enum{OUT,ON,IN};
int contain(const Polygon&,const Point&);
int contain(const Circle&,const Point&);
int contain(const Circle&,const Segment&);
int convex_contain(const Polygon&,const Point&);//O(log |P|)
Int diameter2(Polygon P);
//function list end
Point vec(const Line&s){return s.p2-s.p1;}
Int norm(const Point&p){return p.x*p.x+p.y*p.y;}
Int norm(const Line&s){return norm(vec(s));}
Int dot(const Point&a,const Point&b){return a.x*b.x+a.y*b.y;}
Int cross(const Point&a,const Point&b){return a.x*b.y-a.y*b.x;}
int ccw(const Point&a,const Point&b)
{
	Int crs=cross(a,b);
	return crs>0?COUNTER_CLOCKWISE
		:crs<0?CLOCKWISE
		:dot(a,b)<0?ONLINE_BACK
		:norm(a)<norm(b)?ONLINE_FRONT
		:ON_SEGMENT;
}
int ccw(const Point&a,const Point&b,const Point&c){return ccw(b-a,c-a);}
int ccw(const Line&s,const Point&p){return ccw(s.p1,s.p2,p);}
bool intersect(const Segment&s,const Segment&t){
	return ccw(s,t.p1)*ccw(s,t.p2)<=0&&ccw(t,s.p1)*ccw(t,s.p2)<=0;
}
int N;
int X[50],Y[50],A[50],K[50];
const int a=10000,b=1;
vector<Point>L[50];
int up(int x)
{
	while((x%a+a)%a!=a/2)x++;
	return x;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin>>N;
	int maxa=0;
	for(int i=0;i<N;i++)
	{
		cin>>X[i]>>Y[i]>>A[i];
		maxa=max(maxa,A[i]);
		K[i]=a*X[i]+Y[i];
	}
	vector<int>k(K,K+N);
	sort(k.begin(),k.end());
	vector<int>mid;
	mid.reserve(N+1);
	mid.push_back(k[0]-1);
	for(int i=1;i<N;i++)assert(k[i-1]+1<k[i]);
	for(int i=0;i<N;i++)
	{
		mid.push_back(k[i]+1);
	}
	for(int i=0;i<mid.size();i++)
	{
		for(int x=0;x<maxa;x++)
		{
			//a*X+Y==mid[i]
			int X=x+2000;
			int Y=mid[i]-a*X;
			L[x].push_back(Point(X,Y));
		}
		if(i<k.size())
		{
			int id=0;
			while(K[id]!=k[i])id++;
			for(int x=0;x<A[id];x++)
			{
				L[x].push_back(Point(X[id],Y[id]));
			}
		}
	}
	if(false)
	{//check
		for(int i=0;i<N;i++)
		{
			int cnt=0;
			for(int j=0;j<maxa;j++)
			{
				bool fn=false;
				for(Point p:L[j])if(p==Point(X[i],Y[i]))fn=true;
				if(fn)cnt++;
			}
			assert(cnt==A[i]);
		}
		for(int i=0;i<maxa;i++)
		{
			assert(L[i].size()>=2);
			for(int j=0;j<L[i].size();j++)
			{
				assert(abs(L[i][j].x)<=(int)1e9);
				assert(abs(L[i][j].y)<=(int)1e9);
			}
			for(int j=0;j+1<L[i].size();j++)
			{
				Segment s(L[i][j],L[i][j+1]);
				for(int k=0;k+1<L[i].size();k++)
				{
					if(abs(j-k)<=1)continue;
					Segment t(L[i][k],L[i][k+1]);
					if(intersect(s,t))
					{
						Point p;
						int c=0;
						if(s.p1==t.p1)p=s.p1,c++;
						if(s.p1==t.p2)p=s.p1,c++;
						if(s.p2==t.p1)p=s.p2,c++;
						if(s.p2==t.p2)p=s.p2,c++;
						assert(c==1);
						bool fn=false;
						for(int i=0;i<N;i++)if(p==Point(X[i],Y[i]))fn=true;
						assert(fn);
					}
				}
				for(int k=0;k<maxa;k++)if(k!=i)
				{
					for(int l=0;l+1<L[k].size();l++)
					{
						Segment t(L[k][l],L[k][l+1]);
						if(intersect(s,t))
						{
							Point p;
							int c=0;
							if(s.p1==t.p1)p=s.p1,c++;
							if(s.p1==t.p2)p=s.p1,c++;
							if(s.p2==t.p1)p=s.p2,c++;
							if(s.p2==t.p2)p=s.p2,c++;
							assert(c==1);
							bool fn=false;
							for(int i=0;i<N;i++)if(p==Point(X[i],Y[i]))fn=true;
							assert(fn);
						}
					}
				}
			}
		}
	}
	cout<<maxa<<"\n";
	for(int i=0;i<maxa;i++)
	{
		cout<<L[i].size();
		for(Point p:L[i])cout<<" "<<p.x<<" "<<p.y;
		cout<<"\n";
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3508kb

input:

3
1 2 1
2 1 2
3 3 2

output:

2
7 2000 -19989999 1 2 2000 -19989997 2 1 2000 -19979998 3 3 2000 -19969996
6 2001 -19999999 2001 -19999997 2 1 2001 -19989998 3 3 2001 -19979996

result:

ok ok Sum L = 13

Test #2:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

1
1 1 1

output:

1
3 2000 -19990000 1 1 2000 -19989998

result:

ok ok Sum L = 3

Test #3:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

1
1 1 50

output:

50
3 2000 -19990000 1 1 2000 -19989998
3 2001 -20000000 1 1 2001 -19999998
3 2002 -20010000 1 1 2002 -20009998
3 2003 -20020000 1 1 2003 -20019998
3 2004 -20030000 1 1 2004 -20029998
3 2005 -20040000 1 1 2005 -20039998
3 2006 -20050000 1 1 2006 -20049998
3 2007 -20060000 1 1 2007 -20059998
3 2008 -2...

result:

ok ok Sum L = 150

Test #4:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

50
662 -567 48
728 -120 7
307 669 27
-885 -775 21
100 242 9
-784 -537 41
940 198 46
736 -551 30
-449 456 16
-945 382 18
-182 810 49
213 187 44
853 245 48
617 -305 19
-81 261 3
617 208 8
-548 -652 6
-888 -667 14
-371 -812 43
202 -702 10
-668 -725 5
961 -919 33
-870 -697 50
428 810 29
560 405 7
348 -3...

output:

50
101 2000 -29810194 -981 -193 2000 -29810192 -945 382 2000 -29449617 -926 671 2000 -29259328 -888 -667 2000 -28880666 -885 -775 2000 -28850774 -870 -697 2000 -28700696 -825 381 2000 -28249618 -784 -537 2000 -27840536 -683 731 2000 -26829268 -668 -725 2000 -26680724 -579 -437 2000 -25790436 -558 82...

result:

ok ok Sum L = 3743

Test #5:

score: 0
Accepted
time: 0ms
memory: 3408kb

input:

50
-772 697 1
-756 -909 1
659 923 1
850 471 1
260 -24 1
473 -639 1
-575 393 1
-466 197 1
333 -637 1
-192 -890 1
103 546 1
749 -723 1
-573 613 1
214 -138 1
277 928 1
266 291 1
911 275 1
-680 -67 1
69 190 1
-197 -795 1
684 618 1
729 -115 1
-658 -229 1
-595 -470 1
898 -172 1
401 81 1
133 685 1
223 400 ...

output:

1
101 2000 -27719304 -772 697 2000 -27719302 -756 -909 2000 -27560908 -680 -67 2000 -26800066 -666 -82 2000 -26660081 -658 -229 2000 -26580228 -595 -470 2000 -25950469 -575 393 2000 -25749606 -573 613 2000 -25729386 -571 -716 2000 -25710715 -532 838 2000 -25319161 -530 890 2000 -25299109 -466 197 20...

result:

ok ok Sum L = 101

Test #6:

score: 0
Accepted
time: 1ms
memory: 3456kb

input:

50
-56 747 3
993 -490 4
930 -139 1
-298 -330 1
938 -351 5
-973 100 5
-472 44 4
345 628 5
481 -91 4
789 581 5
457 -29 4
871 -799 1
692 994 4
699 854 2
893 -33 1
-483 256 3
-962 -540 2
846 -893 1
830 609 5
845 -383 2
-552 -966 1
-544 -51 1
564 186 4
-615 -675 1
618 -911 3
-561 -302 4
-293 667 3
-334 -...

output:

5
101 2000 -29989671 -999 330 2000 -29989669 -973 100 2000 -29729899 -962 -540 2000 -29620539 -888 -613 2000 -28880612 -842 381 2000 -28419618 -792 -625 2000 -27920624 -637 -801 2000 -26370800 -615 -675 2000 -26150674 -561 -302 2000 -25610301 -552 -966 2000 -25520965 -544 -51 2000 -25440050 -483 256...

result:

ok ok Sum L = 396

Test #7:

score: 0
Accepted
time: 1ms
memory: 3464kb

input:

50
600 997 5
-893 -204 3
408 443 1
-560 -748 7
-647 161 6
-285 -980 1
87 -582 7
-48 -721 7
997 285 2
-189 -728 8
525 222 4
-324 816 9
760 317 3
753 -480 10
-813 -921 3
-325 -875 8
-747 816 10
-627 605 7
775 786 6
136 -54 2
274 948 10
216 -113 7
924 68 3
101 576 8
60 -501 2
898 801 8
-767 -974 10
-99...

output:

10
101 2000 -29820213 -982 -212 2000 -29820211 -980 753 2000 -29799246 -972 -312 2000 -29720311 -893 -204 2000 -28930203 -813 -921 2000 -28130920 -805 -304 2000 -28050303 -767 -974 2000 -27670973 -747 816 2000 -27469183 -660 -335 2000 -26600334 -647 161 2000 -26469838 -627 605 2000 -26269394 -560 -7...

result:

ok ok Sum L = 791

Test #8:

score: 0
Accepted
time: 1ms
memory: 3524kb

input:

50
24 -889 49
117 418 49
25 524 44
980 -416 43
-494 357 41
-287 -285 46
151 574 41
-289 68 49
-515 -540 41
-367 -178 47
-887 151 45
197 -272 47
714 724 45
-737 94 49
810 830 47
808 -695 41
537 -637 49
-142 -167 44
-749 -631 47
445 -444 42
801 910 43
59 363 42
-912 466 50
-649 -479 48
-958 -511 49
88...

output:

50
101 2000 -29979658 -998 343 2000 -29979656 -958 -511 2000 -29580510 -912 466 2000 -29119533 -887 151 2000 -28869848 -868 -114 2000 -28680113 -786 -384 2000 -27860383 -749 -631 2000 -27490630 -737 94 2000 -27369905 -649 -479 2000 -26490478 -615 809 2000 -26149190 -588 -138 2000 -25880137 -515 -540...

result:

ok ok Sum L = 4818

Test #9:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

50
151 -171 50
-367 -951 50
808 569 50
150 -618 50
27 -476 50
-846 729 50
549 -456 50
50 646 50
294 -70 50
-571 104 50
128 -265 50
913 -700 50
267 -965 50
896 846 50
-2 713 50
21 679 50
-515 975 50
168 180 50
-369 -98 50
676 115 50
643 -779 50
920 -237 50
-324 450 50
149 -378 50
-882 -602 50
-126 -7...

output:

50
101 2000 -28820603 -882 -602 2000 -28820601 -851 279 2000 -28509720 -846 729 2000 -28459270 -841 601 2000 -28409398 -604 -168 2000 -26040167 -571 104 2000 -25709895 -544 307 2000 -25439692 -515 975 2000 -25149024 -501 927 2000 -25009072 -474 780 2000 -24739219 -369 -98 2000 -23690097 -367 -951 20...

result:

ok ok Sum L = 5050

Test #10:

score: -100
Runtime Error

input:

50
4 5 34
1 -5 24
-4 -4 32
-3 3 28
0 -1 21
1 -4 25
0 0 30
0 -4 42
-3 -2 44
-5 -3 37
4 -1 46
5 2 20
2 2 37
-2 5 35
-2 -1 39
2 4 32
-4 -3 42
0 3 32
3 5 47
-4 1 2
5 -1 17
-5 -4 5
-2 2 29
-5 1 11
2 -5 43
4 4 14
-5 0 9
0 -5 17
5 1 27
-3 0 24
-1 4 16
5 0 50
3 -2 18
1 -2 6
2 -1 29
-1 3 38
1 5 36
-3 1 28
-3...

output:


result: