QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#718999#7680. SubwaydezexWA 2ms4100kbC++204.8kb2024-11-06 22:00:122024-11-06 22:00:13

Judging History

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

  • [2024-11-06 22:00:13]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:4100kb
  • [2024-11-06 22:00:12]
  • 提交

answer

#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;
typedef long double db;
const db eps = 1e-8;
typedef long long ll;
int sgn(db x)
{
    if(fabs(x) < eps) return 0;
    if(x < 0) return -1;
    else return 1;
}

struct Point
{
    db x,y;
    Point(){}
    Point(db x_, db y_):x(x_),y(y_){}
    
    Point operator - (const Point& b){return Point(x-b.x,y-b.y);}
    db operator ^ (const Point& b){
        return x*b.y - y*b.x;
    }
    bool operator < (Point b) const {return sgn(x-b.x)==0?sgn(y-b.y)<0:x<b.x;}
    bool operator == (Point b) const {return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;}
    bool operator <= (Point b) const {return sgn(x-b.x)==0?sgn(y-b.y)<=0:x<b.x;}
    Point operator *(const double &k)const{
		return Point(x*k,y*k);
	}
    db distance(Point p){
		return hypot(x-p.x,y-p.y);
	}
    void input(){
		scanf("%Lf %Lf",&x,&y);
	}
	void output(){
		printf("%.2f %.2f\n",x,y);
	}
};

struct Line
{
    Point s,e;
    Line(){}
    Line(Point s_, Point e_):s(s_),e(e_){}
    Line(db a, db b, db c)
    {
        if(sgn(a) == 0)
        {
            s = Point(0, -c/b);
            e = Point(1, -c/b);
        } else if(sgn(b) == 0)
        {
            s = Point(-c/a, 0);
            e = Point(-c/a, 1); 
        } else 
        {
            s = Point(0, -c/b);
            e = Point(1, (-c-a)/b);
        }
    }

    Point crosspoint(Line v)
    {
        // printf("crossing:\n");
        // s.output();e.output();
        // printf("with\n");
        // v.s.output();v.e.output();
        db a1 = (v.e-v.s)^(s-v.s);
        db a2 = (v.e-v.s)^(e-v.s);
        // printf("a1:%.10Lf a2:%.10Lf\n",a1,a2);
        // printf("res:");
        // printf("%.2Lf %.2Lf\n",(s.x*a2-e.x*a1)/(a2-a1), (s.y*a2-e.y*a1)/(a2-a1));
        // printf("a2-a1=%.10Lf\n",a2-a1);
        // printf("a2-a1=%.10Lf\n",db((ll)a2-(ll)a1));
        
        // printf("a2/(a2-a1)=%.10Lf\n",a2/(a2-a1));
        return Point(s.x*(a2/(a2-a1))-e.x*(a1/(a2-a1)), s.y*(a2/(a2-a1))-e.y*(a1/(a2-a1))); 
    }
    int linecrossseg(Line v)
    {
        // printf("crossing:\n");
        // s.output();e.output();
        // printf("with\n");
        // v.s.output();v.e.output();
		int d1 = sgn((e-s)^(v.s-s));
		int d2 = sgn((e-s)^(v.e-s));
		if((d1^d2)==-2) return 2;
		return (d1==0||d2==0);
	}
    bool parallel(Line v){
		return sgn((e-s)^(v.e-v.s)) == 0;
	}
    int relation(Point p){
		int c = sgn((p-s)^(e-s));
		if(c < 0)return 1;
		else if(c > 0)return 2;
		else return 3;
	}
    int linecrossline(Line v){
		if((*this).parallel(v))
			return v.relation(s)==3;
		return 2;
	}
    db length(){
		return s.distance(e);
	}
    db dispointtoline(Point p){
		return fabs((p-s)^(e-s))/length();
	}

};

db cross(Point A,Point B,Point C){
	return (B-A)^(C-A);
}


struct Ele
{
    Point s,e;
    int cnt;
};

const int N=60;
Point u(10001,2);
Point v(-2, 10001);
int n;

Point p[N];
int a[N];
// Line l[N];
Point mid[N];
Ele e[N];


bool cmp(const Ele& a, const Ele& b)
{
    return a.s < b.s;
}

int main()
{
    scanf("%d",&n);
    Line ax(Point(0,0), u);
    for(int i=1;i<=n;i++)
    {
        p[i].input();
        scanf("%d",&a[i]);
        Point pt = ax.crosspoint(Line(p[i], p[i]-v));
        e[i]=Ele{pt, p[i], a[i]};
        // l[i]=Line(pt, p[i]);
    };
    sort(e+1,e+n+1,cmp);
    for(int i=1;i<=n;i++)
        p[i]=e[i].e;
    for(int i=1;i<=n;i++)
        a[i]=e[i].cnt;
    for(int i=2;i<=n;i++)
    {
        Point pt = p[i];
        pt.y-=1;
        if(pt == p[i])
        {
            pt.y += 0.5;
            pt.x += v.x/2;
            pt.y += v.y/2;
        };
        mid[i]=pt;
    };

    int mx=0;
    for(int i=1;i<=n;i++)
        mx=max(mx, a[i]);
    printf("%d\n",mx);
    for(int i=mx;i>=1;i--)
    {
        // 特殊情况 只有一个点
        int st=1,ed=n;
        while(a[st] < i) st++;
        while(a[ed] < i) ed--;
        vector<Point> ans;
        if(st<ed)
        {
            ans.push_back(p[st]);
            for(int j=st+1;j<=ed;j++)
            {
                ans.push_back(mid[j]-v*i);
                if(a[j] >= i)
                    ans.push_back(p[j]);
                else 
                    ans.push_back(p[j] - v*i);
            };
        } else 
        {
            if(st==1)
            {
                ans.push_back(p[1]);
                ans.push_back(mid[2]-v*i);
            } else 
            {
                ans.push_back(mid[st]-v*i);
                ans.push_back(p[st]);
            }
        }
        printf("%u ",ans.size());
        for(auto pt:ans)
            printf("%.0Lf %.0Lf ",pt.x,pt.y);
        printf("\n");
    };
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3916kb

input:

3
1 2 1
2 1 2
3 3 2

output:

2
3 2 1 7 -20000 3 3 
5 1 2 4 -10001 2 1 5 -9999 3 3 

result:

ok ok Sum L = 8

Test #2:

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

input:

1
1 1 1

output:

1
2 1 1 2 -10001 

result:

ok ok Sum L = 2

Test #3:

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

input:

1
1 1 50

output:

50
2 1 1 100 -500050 
2 1 1 98 -490049 
2 1 1 96 -480048 
2 1 1 94 -470047 
2 1 1 92 -460046 
2 1 1 90 -450045 
2 1 1 88 -440044 
2 1 1 86 -430043 
2 1 1 84 -420042 
2 1 1 82 -410041 
2 1 1 80 -400040 
2 1 1 78 -390039 
2 1 1 76 -380038 
2 1 1 74 -370037 
2 1 1 72 -360036 
2 1 1 70 -350035 
2 1 1 68...

result:

ok ok Sum L = 100

Test #4:

score: 0
Accepted
time: 2ms
memory: 3828kb

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
43 -870 -697 -725 -499670 -725 -499669 -684 -500588 -684 -500587 -583 -499320 -583 -499319 -568 -500776 -568 -500775 -479 -500488 -479 -500487 -458 -499226 -458 -499225 -448 -500703 -448 -500702 -399 -500228 -399 -500227 -369 -500307 -369 -500306 -362 -500770 -362 -500769 -349 -499595 -349 -49959...

result:

ok ok Sum L = 4534

Test #5:

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

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
99 -772 697 -754 -10911 -756 -909 -678 -10069 -680 -67 -664 -10084 -666 -82 -656 -10231 -658 -229 -593 -10472 -595 -470 -573 -9609 -575 393 -571 -9389 -573 613 -569 -10718 -571 -716 -530 -9164 -532 838 -528 -9112 -530 890 -464 -9805 -466 197 -387 -9294 -389 708 -344 -9544 -346 458 -302 -9105 -304 ...

result:

ok ok Sum L = 99

Test #6:

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

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
95 -973 100 -952 -50546 -952 -50545 -878 -50619 -878 -50618 -832 -49625 -832 -49624 -782 -50631 -782 -50630 -627 -50807 -627 -50806 -605 -50681 -605 -50680 -551 -50308 -551 -50307 -542 -50972 -542 -50971 -534 -50057 -534 -50056 -473 -49750 -473 -49749 -462 -49962 -462 -49961 -354 -49837 -354 -4983...

result:

ok ok Sum L = 489

Test #7:

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

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
75 -767 -974 -727 -99195 -747 816 -640 -100346 -640 -100345 -627 -99850 -627 -99849 -607 -99406 -607 -99405 -540 -100759 -540 -100758 -478 -100469 -478 -100468 -399 -99447 -399 -99446 -377 -100752 -377 -100751 -329 -100174 -329 -100173 -305 -100886 -305 -100885 -304 -99195 -304 -99194 -293 -10100...

result:

ok ok Sum L = 890

Test #8:

score: 0
Accepted
time: 2ms
memory: 3888kb

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
37 -912 466 -787 -499900 -787 -499899 -768 -500165 -868 -114 -686 -500435 -686 -500434 -649 -500682 -649 -500681 -637 -499957 -637 -499956 -549 -500530 -549 -500529 -515 -499242 -515 -499241 -488 -500189 -488 -500188 -415 -500591 -415 -500590 -394 -499694 -394 -499693 -386 -499185 -386 -499184 -2...

result:

ok ok Sum L = 4830

Test #9:

score: 0
Accepted
time: 2ms
memory: 3828kb

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
99 -882 -602 -751 -499772 -851 279 -746 -499322 -846 729 -741 -499450 -841 601 -504 -500219 -604 -168 -471 -499947 -571 104 -444 -499744 -544 307 -415 -499076 -515 975 -401 -499124 -501 927 -374 -499271 -474 780 -269 -500149 -369 -98 -267 -501002 -367 -951 -235 -499995 -335 56 -224 -499601 -324 4...

result:

ok ok Sum L = 4950

Test #10:

score: -100
Wrong Answer
time: 2ms
memory: 3820kb

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:

50
2 105 -500051 5 0 
77 -3 -1 95 -490050 95 -490049 95 -490049 95 -490048 95 -490047 95 -490046 95 -490045 95 -490044 96 -490055 96 -490054 96 -490051 96 -490050 96 -490048 96 -490047 96 -490045 96 -490044 97 -490054 97 -490053 97 -490047 97 -490046 97 -490046 97 -490045 97 -490045 97 -490044 98 -4...

result:

wrong answer Duplicated points on polyline 2.