Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- ifstream fin ("mosia1.in");
- ofstream fout ("mosia1.out");
- const int Nmax = 205;
- int n, st[Nmax], top;
- double dp[Nmax];
- struct P
- {
- double ox, oy , dist;
- };
- P a[Nmax];
- bool viz[Nmax];
- inline bool CMP(const P A, const P B)
- {
- if(A . oy == B . oy)
- return A . ox < B . ox;
- return A . oy < B . oy;
- }
- inline double CHECK(int i, int j, int k)
- {
- return (a[i] . ox * a[j] . oy + a[i] . oy * a[k] . ox + a[j] . ox * a[k] . oy
- - a[k] . ox * a[j] . oy - a[j] . ox * a[i] . oy - a[i] . ox * a[k] . oy);
- }
- inline void Solve()
- {
- ++top;
- st[1] = 1;
- ++top;
- st[top] = 2;
- viz[2] = true;
- for(int i = 3 ; i <= n ; i++)
- {
- while(top > 1 && CHECK(st[top - 1], st[top], i) < 0)
- {
- viz[st[top]] = false;
- top--;
- }
- ++top;
- st[top] = i;
- viz[i] = true;
- }
- for(int i = n ; i >= 1 ; i--)
- if(!viz[i]) /// nu se afla in infasuratoare
- {
- while(top > 1 && CHECK(st[top - 1], st[top], i) < 0)
- {
- viz[st[top]] = false;
- top--;
- }
- ++top;
- st[top] = i;
- viz[i] = true;
- }
- top--;
- ///for(int i = 1 ; i <= top ; i++)
- ///fout << st[i] << " ";
- }
- inline double Dist(int i , int j)
- {
- return sqrt((a[j].ox - a[i] . ox) * (a[j].ox - a[i].ox) +
- (a[j].oy - a[i].oy) * (a[j].oy - a[i].oy));
- }
- inline void DP()
- {
- /// dp[i] = aria maxima obtinuta din primele i
- /// alegand obligatoriu punctul st[1]
- double sol;
- dp[1] = Dist(st[n] , st[2]) * a[st[1]].dist / 2;
- dp[2] = dp[1];
- for(int i = 3 ; i < n ; i++)
- {
- dp[i] = max(dp[i - 1] , dp[i - 2] + Dist(st[i - 1] , st[i + 1]) * a[st[i]].dist / 2);
- }
- sol = dp[n - 1];
- /// dp[i] = aria maxima obtinuta din primele i
- /// alegand obligatoriu punctul st[2]
- dp[1] = 0;
- dp[2] = Dist(st[1] , st[3]) * a[st[2]].dist / 2;
- for(int i = 3 ; i <= n ; i++)
- {
- dp[i] = max(dp[i - 1] , dp[i - 2] + Dist(st[i - 1] , st[i + 1]) * a[st[i]].dist / 2);
- }
- sol = max(sol , dp[n]);
- fout << fixed << setprecision(6) << sol << "\n";
- }
- int main()
- {
- fin >> n;
- for(int i = 1 ; i <= n ; i++)
- fin >> a[i] . ox >> a[i] . oy >> a[i] . dist;
- sort(a + 1, a + n + 1, CMP);
- Solve();
- DP();
- fin.close();
- fout.close();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement