11473 - Campus Roads

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Monsoon
Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

11473 - Campus Roads

Post by Monsoon » Mon Aug 04, 2008 12:22 pm

One question to understand the problem statement, what is answer for this case

Code: Select all

1
7 3
0 0
2 0
2 1
1 1
1 -1
4 -1
4 0
i.e. i think this case doesn't have largest gap, because 5 is supremum but you can't achieve that (tree located at intersection), and for each E>0 you can achieve 5-E (move tree from P1 2E to the left)

ok, so my question is exactly: are intersecting segments important to us?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11473 - Campus Roads

Post by emotional blind » Mon Aug 04, 2008 1:10 pm

Intersecting segments are not important for this problem. You should ignore all intersections, other then intermediate points P(2), P(3), .., P(K-1).

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 11473 - Campus Roads

Post by RC's » Mon Aug 04, 2008 10:21 pm

Can you please give some input / output for this problem, and of course the output from the input provided by Monsoon ?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11473 - Campus Roads

Post by emotional blind » Tue Aug 05, 2008 7:04 am

Output of Monsoon's input:

Code: Select all

Road #1:
0.00 0.00
1.00 0.00
4.00 0.00

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 11473 - Campus Roads

Post by RC's » Thu Aug 07, 2008 4:56 pm

Hm.. My program outputs the same as yours, but I get WA.. Please check this input

Code: Select all

5
84 6
-445.13 347.11
727.97 694.64
321.35 -702.51
490.54 475.34
-957.03 -867.61
412.11 154.72
504.52 752.62
-974.73 -571.11
735.84 -286.01
-273.80 918.82
444.89 -821.47
170.29 -766.48
79.71 -20.75
328.25 51.64
831.24 860.72
14.47 786.56
890.50 957.52
-299.19 -605.53
-727.72 -425.84
-571.84 890.87
517.33 -672.36
-372.38 135.56
586.24 -283.87
664.92 450.26
-742.98 -824.04
919.80 630.37
-660.58 689.09
212.83 -85.63
17.76 -995.79
392.70 -528.02
635.56 533.33
-103.94 -25.33
233.58 -13.00
92.35 -188.84
-845.15 810.00
226.62 -490.84
28.08 -519.84
772.09 927.06
442.87 733.70
5.86 777.95
628.66 -222.05
-380.80 -952.76
449.89 555.54
175.96 -131.41
-969.48 121.34
231.08 -581.97
-680.42 195.74
-78.49 391.30
910.77 -44.37
842.41 -375.12
-571.59 -873.47
-978.88 424.38
-207.52 -561.89
801.15 162.60
-325.38 -495.06
448.97 709.35
458.68 -803.77
-704.47 255.92
17.09 555.73
-773.74 96.50
616.52 -664.79
330.32 929.44
264.65 203.92
-476.99 239.99
811.22 -304.20
-46.51 -671.81
-884.95 -42.11
9.46 -456.73
590.33 -637.88
-267.15 287.90
-555.97 -957.82
-542.48 354.37
917.48 -580.44
482.54 -844.73
-155.76 -220.03
592.71 -588.81
836.79 962.65
239.56 -141.78
414.61 226.26
195.19 -463.07
386.60 352.54
490.48 226.38
799.19 50.66
-548.16 585.08
72 27
647.71 561.28
476.14 -330.02
557.56 -364.69
737.98 749.21
776.37 -543.27
-702.88 631.04
-433.23 438.11
314.88 -367.00
570.80 868.90
275.88 -756.16
-504.88 110.60
651.12 -616.52
580.87 437.07
627.81 -536.07
-328.92 -918.40
-781.98 -686.71
-311.16 -946.41
-941.35 -974.43
-662.66 287.05
-784.36 -201.11
835.82 -315.80
-696.17 824.34
-497.56 -384.70
236.82 288.21
998.23 -561.40
-82.82 -450.01
-957.52 -397.77
-818.66 558.53
-585.45 890.50
310.36 -430.73
-947.57 377.01
-580.08 -775.70
61.77 648.07
-958.37 58.78
-552.19 -143.01
208.25 -505.00
381.90 -825.81
355.16 -612.30
-183.65 -806.88
351.14 182.68
258.67 -143.19
969.97 750.73
519.35 -534.55
116.46 -39.73
-755.98 -670.72
-881.16 -949.28
43.58 -371.89
-600.59 868.96
34.61 -959.47
-162.35 -968.32
602.29 -295.04
136.29 -923.83
198.43 75.56
504.39 661.44
-12.70 -765.26
968.87 883.30
151.49 -774.41
627.99 -235.47
-329.59 966.25
158.20 -16.30
-615.84 308.59
-112.30 -95.03
-845.21 -195.92
748.78 -29.60
937.87 739.26
421.81 -480.90
576.66 -996.70
-17.27 93.75
131.59 -650.27
-632.81 298.40
-442.99 -384.52
963.62 269.47
5 83
-352.29 822.33
302.80 -816.65
570.68 -663.64
212.46 -803.89
-986.08 -559.02
50 80
-377.14 564.27
-835.33 -934.88
-668.21 408.14
-790.59 736.94
-707.09 411.44
-909.97 770.69
121.70 -736.15
129.33 23.44
-228.70 533.02
343.99 -714.36
347.90 -532.47
286.07 -992.13
-819.52 -961.73
-831.12 172.06
456.97 280.40
91.06 -129.94
738.83 998.66
170.53 151.37
667.54 -101.44
401.31 -296.81
174.68 205.63
-955.02 924.74
-491.21 -164.25
-629.21 -40.95
-609.50 178.41
-445.19 243.47
609.86 556.15
-447.57 -856.69
376.89 421.88
755.80 229.06
-261.17 357.30
-750.92 761.11
-623.41 -65.73
473.57 943.85
91.74 -497.50
115.72 511.90
-701.42 -35.03
-969.85 -789.00
-168.40 -395.69
-989.56 735.29
382.32 22.58
-779.79 685.12
-122.44 256.65
96.44 105.90
-888.49 -867.68
538.21 -827.70
-55.97 918.21
-806.76 578.98
-621.70 344.24
-345.64 -799.26
86 68
378.60 -414.49
-102.54 490.78
-858.34 -159.30
955.87 -527.59
839.78 -522.28
-129.82 -805.24
452.09 -224.98
-842.71 49.99
-24.72 224.18
898.44 -872.99
-856.51 -380.49
-280.58 522.28
746.28 -644.59
-851.14 -485.78
355.90 -507.02
-331.60 -337.46
-721.74 -841.19
-233.28 896.85
538.21 -162.11
309.75 -344.60
712.77 -875.73
-459.78 -862.98
-575.32 -509.58
-982.12 729.61
-691.47 -360.66
-185.55 676.03
261.66 -999.21
-725.40 -958.86
793.33 934.69
-344.54 -957.70
283.81 -796.14
958.50 -194.52
965.70 -720.83
-735.78 609.44
-558.96 -961.06
884.09 -318.97
545.96 425.42
-359.07 -396.30
-625.12 620.67
-409.30 401.49
278.38 304.93
498.66 361.82
645.08 -441.16
381.41 -341.25
282.35 973.51
427.98 839.23
206.12 529.05
612.49 -764.16
-345.89 -193.54
-689.51 -632.69
-866.15 92.83
-767.94 389.77
318.30 -55.85
983.28 661.62
601.99 767.94
569.58 484.01
-870.61 -12.94
152.71 -920.47
108.76 348.88
374.45 871.70
223.45 941.10
-441.35 -871.95
-46.57 476.99
105.35 28.32
-380.49 413.09
-611.63 -778.32
-37.23 460.94
-530.58 -65.67
71.35 56.03
940.92 690.25
467.77 346.74
-789.12 -291.81
168.76 264.34
540.77 36.56
-469.85 -761.47
150.57 489.20
-310.55 119.20
-297.73 444.46
418.76 868.47
474.79 -429.87
-799.74 583.86
-456.67 536.44
-663.45 417.18
-725.71 -219.91
-90.94 949.04
-550.17 381.47
My program outputs :

Code: Select all

Road #1:
-445.13 347.11
101.35 803.52
536.42 100.06
706.77 -422.93
516.11 -179.53
-548.16 585.08

Road #2:
647.71 561.28
758.38 62.24
-444.78 446.37
492.86 439.42
-140.75 -118.44
620.40 -382.40
-891.73 -972.22
180.40 -269.40
-656.44 582.49
794.52 -334.09
-879.41 140.17
-15.38 -221.57
-377.00 -325.21
-450.54 -191.40
258.22 10.74
594.36 -320.61
-401.96 -650.08
-309.02 29.67
275.56 -735.91
192.38 -199.42
840.03 622.00
294.26 183.35
-499.98 259.96
448.80 -60.90
535.00 -857.94
-286.58 -131.29
963.62 269.47

Road #3:
-352.29 822.33
-335.63 780.64
-318.96 738.95
-302.30 697.26
-285.64 655.57
-268.97 613.88
-252.31 572.19
-235.65 530.50
-218.98 488.81
-202.32 447.12
-185.66 405.43
-168.99 363.74
-152.33 322.05
-135.67 280.36
-119.00 238.67
-102.34 196.98
-85.68 155.29
-69.01 113.60
-52.35 71.91
-35.69 30.22
-19.02 -11.47
-2.36 -53.16
14.30 -94.85
30.97 -136.54
47.63 -178.23
64.29 -219.92
80.96 -261.61
97.62 -303.30
114.28 -344.99
130.94 -386.68
147.61 -428.37
164.27 -470.06
180.93 -511.75
197.60 -553.44
214.26 -595.13
230.92 -636.82
247.59 -678.51
264.25 -720.20
280.91 -761.89
297.58 -803.58
329.57 -801.36
368.55 -779.09
407.54 -756.82
446.52 -734.56
485.51 -712.29
524.49 -690.02
563.48 -667.75
536.59 -676.99
494.79 -693.35
452.98 -709.72
411.17 -726.09
369.37 -742.46
327.56 -758.83
285.75 -775.19
243.95 -791.56
201.60 -801.67
157.61 -792.68
113.62 -783.70
69.64 -774.71
25.65 -765.72
-18.34 -756.74
-62.33 -747.75
-106.32 -738.76
-150.30 -729.77
-194.29 -720.79
-238.28 -711.80
-282.27 -702.81
-326.26 -693.83
-370.25 -684.84
-414.23 -675.85
-458.22 -666.87
-502.21 -657.88
-546.20 -648.89
-590.19 -639.90
-634.17 -630.92
-678.16 -621.93
-722.15 -612.94
-766.14 -603.96
-810.13 -594.97
-854.12 -585.98
-898.10 -576.99
-942.09 -568.01
-986.08 -559.02

Road #4:
-377.14 564.27
-549.03 1.87
-720.92 -560.53
-811.05 -739.75
-738.43 -156.17
-674.98 426.33
-726.82 488.33
-855.67 691.38
-523.44 206.14
-191.22 -279.11
122.04 -701.97
127.95 -113.92
-129.78 392.23
-55.12 154.95
190.25 -379.49
342.88 -569.80
124.18 -987.68
-463.68 -971.51
-821.89 -729.64
-827.91 -141.59
-557.68 195.06
28.33 244.35
351.86 162.53
188.74 40.24
481.48 550.28
699.23 939.62
371.65 451.22
372.88 48.44
459.95 -253.78
189.42 172.96
-291.18 502.17
-787.28 817.96
-802.50 566.63
-572.06 25.58
-611.61 154.95
-73.37 353.66
490.47 520.77
332.10 185.03
-20.28 -285.79
-372.66 -756.60
-196.62 -467.52
122.07 26.71
481.95 368.42
477.20 264.19
-106.26 337.77
-594.44 632.09
-692.20 380.35
-522.80 26.86
-90.09 425.10
342.63 823.34
368.55 547.40
217.95 -21.07
94.00 -402.31
107.97 185.60
-101.75 366.34
-590.46 39.24
-853.88 -463.26
-752.32 -682.25
-224.39 -423.17
-477.27 29.72
-822.79 505.59
-719.59 595.04
-197.74 323.93
324.12 52.82
-71.59 281.36
-582.47 572.63
-477.41 488.02
12.92 163.42
-249.68 -236.23
-667.92 -649.65
-610.67 -859.89
-22.82 -843.42
529.57 -802.30
340.10 -245.58
150.63 311.14
-38.84 867.87
-543.42 697.96
-621.65 344.05
-483.65 -227.60
-345.64 -799.26

Road #5:
378.60 -414.49
-284.20 334.53
-360.99 -260.26
878.53 -511.89
-87.60 -763.14
-39.60 -120.56
-408.67 142.42
536.85 -443.24
221.43 -683.00
-778.41 -258.06
-56.50 267.65
696.90 -639.68
-561.70 -514.56
122.64 -502.92
-529.63 -593.15
-464.42 74.40
8.43 565.07
353.70 -402.52
42.03 -868.44
-697.32 -137.94
-891.53 389.78
-477.38 78.04
-30.95 96.91
131.47 -993.89
-470.62 -641.20
320.73 345.45
530.81 498.09
-120.95 -585.85
419.74 -674.93
952.62 -710.61
-43.79 68.42
-692.55 225.45
-494.28 -932.28
661.29 -418.10
395.40 288.72
-421.27 -158.56
-259.03 380.39
587.39 -124.77
331.73 318.11
214.54 502.25
593.71 -704.38
-399.35 -261.86
-851.32 137.67
156.56 10.50
875.65 691.63
-87.33 257.34
-544.26 -302.37
141.18 -587.43
257.32 641.22
-65.76 152.37
-392.53 -705.15
-35.96 445.66
-419.43 212.40
-504.14 -546.41
-142.86 348.19
138.89 105.29
720.73 530.39
-381.17 -84.55
-91.04 113.50
126.24 -290.77
-245.31 -308.83
-141.11 255.16
323.66 812.19
468.53 -284.75
-401.40 267.03
-680.06 247.20
-346.11 479.14
-550.17 381.47
Is it wrong ?

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11473 - Campus Roads

Post by emotional blind » Thu Aug 07, 2008 5:31 pm

Correct Output.

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Re: 11473 - Campus Roads

Post by RC's » Thu Aug 07, 2008 6:35 pm

Thank you, I got AC now... But I don't know why I got WA in the contest..

pola
New poster
Posts: 2
Joined: Fri Aug 08, 2008 1:15 am

Re: 11473 - Campus Roads

Post by pola » Fri Aug 08, 2008 1:22 am

Can you help me with my code, I have the same results as RC's, but I got Wrong Answer in the judge,

Thanks in advance

Code: Select all

#include <math.h>
#include <iostream>
#include <vector>
using namespace std;

#define FOR(i,s,n) for (int i=(s);i<(n);i++)

double dist(pair<double, double> &p1, pair<double, double> &p2) {
    return hypot(p1.first-p2.first,p1.second-p2.second);
}

void solve(int t,vector<pair<double, double> > &g) {
    double d = 0.0;
    vector<double> ds(g.size());
    vector<double> dsa(g.size());
    vector<pair<double,double> > df(g.size());
    FOR(i,1,g.size()) {
        ds[i] = dist(g[i-1],g[i]);
        dsa[i] = dsa[i-1]+ds[i];
        df[i].first = g[i].first - g[i-1].first;
        df[i].second = g[i].second - g[i-1].second;
        d += ds[i];
    }
    double seg = d/(t-1);

    double covered=0;
    cout << fixed;
    cout.precision(2);
    cout << g[0].first << " " << g[0].second << endl;
    FOR(i,1,t) {
        covered += seg;
        int j=0;
        while(dsa[j] < covered && j < dsa.size()-1) ++j;

        double d = dsa[j] - covered;
        double D = ds[j];

        double x = g[j].first - df[j].first * d / (D ? D : 1.0);
        double y = g[j].second - df[j].second * d / (D ? D : 1.0) ;

        cout << x << " " << y << endl;
    }
}

int main() {
    int cases;
    cin >> cases;
	FOR(i,0,cases) {
		vector< pair<double, double> > g;
        int k,t;
        cin >> k >> t;
        FOR(j,0,k) {
            pair<double, double> p;
            cin >> p.first >> p.second;
            g.push_back(p);
        }

        if(i) cout << endl;
        cout << "Road #" << (i+1) << ":" << endl;
        solve(t,g);
	}
	return 0;
}

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Re: 11473 - Campus Roads

Post by emotional blind » Fri Aug 08, 2008 4:14 am

print a new line after each test case.

pola
New poster
Posts: 2
Joined: Fri Aug 08, 2008 1:15 am

Re: 11473 - Campus Roads

Post by pola » Fri Aug 08, 2008 3:07 pm

emotional blind wrote:print a new line after each test case.
That was the problem, what a fool :(

Thank you for your help.

Post Reply

Return to “Volume 114 (11400-11499)”