Cześć, mam problem z zadaniem z spoja: link.
Napisałem taki program:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
struct Point {
int x, y;
};
long double calculateArea(const vector<Point>& vec)
{
long double area = 0.0;
for (int i = 0; i < vec.size()-1; i++) {
if (i == vec.size()-2) {
area += vec[i].x*vec[0].y - vec[i].y*vec[0].x;
} else {
area += vec[i].x*vec[i+1].y - vec[i].y*vec[i+1].x;
}
}
return abs(area/2);
}
int main()
{
int n;
cin >> n;
vector<Point> vec; // tymczasowo przechowuje kazda z linii
vector<long long int> results; // przechowuje wyniki obliczone z pary linii
while (n--) {
// pierwsza linia
vec.clear();
long long int ink = 0;
Point p;
cin >> p.x >> p.y;
vec.push_back(p);
do {
cin >> p.x >> p.y;
vec.push_back(p);
} while (p.x != vec[0].x || p.y != vec[0].y);
long double blackArea = calculateArea(vec);
// druga linia
vec.clear();
cin >> p.x >> p.y;
vec.push_back(p);
do {
cin >> p.x >> p.y;
vec.push_back(p);
} while (p.x != vec[0].x || p.y != vec[0].y);
long double greyArea = calculateArea(vec);
ink += blackArea < greyArea ? blackArea*10 : greyArea*10;
ink += blackArea >= greyArea ? (blackArea-greyArea)*6 : (greyArea-blackArea)*6;
results.push_back(ink);
//getchar();
}
for (auto e : results) {
cout << e << endl;
}
return 0;
}
dla testowych danych dostaje dwa błedne wyniki:
wejście:
18
5 4 3 8 9 2 2 5 -3 2 6 -4 3 -2 1 9 -9 -4 4 4 -4 3 -1 -5 -6 4 3 0 2 1 9 4 2 0 3 -4 5 4
9 3 0 4 -3 2 5 -6 3 -4 7 6 -3 2 7 -6 8 4 3 -6 9 4 -5 9 1 -1 9 4 7 2 -5 2 7 -8 -3 2 -2 1 0 4 0 5 6 -3 9 3
3634 346 35 346 34 346 34 634543 34634 346 43 346346 87 3 903463 34 34 34632 6346 25626 34578 7894 4326 4372 65357 23632 67432 76321 67622 356 3634 346
89540 34530 349 345 3045 4603 9343 -4563 -435 3423 2343 -3456 353 -3235 -8765 2345 -6322 225 -551525 3632 -62523 63252 -5526 65252 -63236 6332 89540 34530
89540 34530 349 345 3045 4603 9343 -4563 -435 3423 2343 -3456 353 -3235 -8765 2345 -6322 225 -551525 3632 -62523 63252 -5526 65252 -63236 6332 89540 34530
3634 346 35 346 34 346 34 634543 34634 346 43 346346 87 3 903463 34 34 34632 6346 25626 34578 7894 4326 4372 65357 23632 67432 76321 67622 356 3634 346
5 6 7 8 3 -5 2 -6 3 5 5 6
-5 -6 -7 -8 -3 5 -2 6 -3 -5 -5 -6
5 -3 1 4 -6 2 06 3 -2 9 5 -3
6 3 6 2 9 4 6 -2 7 -3 4 0 6 3
09 -05 3 9 04 5 03 5 014 4 5 2 345 23 2 -03 09 -05
9 4 -3 5 -3 43 -53 -3433 35 3 4 -5 -03 2 -2 -5 -4 2 -6 0 9 4
1 7 9 3 1 7
1 7 9 3 1 7
0 5 3 1 5 2 6 9 0 3 6 6 0 5
9 4 3 -7 -2 7 7 4 -6 -7 3 -2 -6 0 9 3 9 4
1 1 1 1
0 5 3 1 5 2 6 9 0 3 6 6 0 5
1 9 1 9
9 4 9 4
5 3 4 5 5 4 6 5 5 3
8 8 6 4 8 0 5 3 2 0 4 4 2 8 5 5 8 8
-1 1 0 0 1 1 0 -1 -1 1
-3 4 0 1 3 4 1 0 3 -4 0 -1 -3 -4 -1 0 -3 4
50000 30000 40000 50000 50000 40000 60000 50000 50000 30000
80000 80000 60000 40000 80000 0 50000 30000 20000 0 40000 40000 20000 80000 50000 50000 80000 80000
-10000 10000 0 0 10000 10000 0 -10000 -10000 10000
-30000 40000 0 10000 30000 40000 10000 0 30000 -40000 0 -10000 -30000 -40000 -10000 0 -30000 40000
8 8 6 4 8 0 5 3 2 0 4 4 2 8 5 5 8 8
5 3 4 5 5 4 6 5 5 3
-3 4 0 1 3 4 1 0 3 -4 0 -1 -3 -4 -1 0 -3 4
-1 1 0 0 1 1 0 -1 -1 1
1 2 2 1 2 2 1 2
0 2 3 0 2 3 0 2
2 3 5 2 3 3 5 4 2 3
1 5 1 3 5 0 3 2 5 1 6 2 4 3 6 3 6 4 7 4 7 1 6 1 6 0 8 0 8 5 1 5
wyjście:
1360
12404485333 -- źle
12404485333 -- źle
240
164
400136
0
512
147
0
88
88
8800000000
8800000000
88
88
23
139
Próbowałem inny algorytm do wyznaczania pola, ale to nie pomogło. Typy danych chyba są wystarczająco pojemne. Póki co nie mam pomysłu, gdzie może być błąd. Z góry dzięki za wszelkie wskazówki.