Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // adam.cpp : Defines the entry point for the console application.
- //
- #include "stdafx.h"
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <fstream>
- #include <utility>
- #include <cmath>
- #define MAX 50001
- #define PI 3.141592
- using namespace std;
- vector < pair<long long, long long> >large_lantern;
- vector < pair<long long, long long> >small_lantern;
- vector < pair<double, int> >tangens;
- vector < pair<long long, long long> >ok;
- int large_amount;
- int small_amount;
- int stos[MAX];
- int index = 0;
- fstream plik("sjf.out", std::ios::out);
- bool det(int A, int B, int C)
- {
- long long wyznacznik = large_lantern[A].second*large_lantern[B].first + large_lantern[B].second*large_lantern[C].first + large_lantern[C].second*large_lantern[A].first - large_lantern[C].second*large_lantern[B].first - large_lantern[A].second*large_lantern[C].first - large_lantern[B].second*large_lantern[A].first;
- if (wyznacznik>0)
- return 1;
- return 0;
- }
- int wyznacznik_ppl(int A, int B)
- {
- A = stos[A];
- B = stos[B];
- long long wyznacznik_ppl = large_lantern[A].second*large_lantern[B].first + large_lantern[B].second*small_lantern[small_lantern.size() - 1].first + small_lantern[small_lantern.size() - 1].second*large_lantern[A].first - large_lantern[A].first*large_lantern[B].second - large_lantern[B].first*small_lantern[small_lantern.size() - 1].second - small_lantern[small_lantern.size() - 1].first*large_lantern[A].second;
- if (wyznacznik_ppl >= 0)
- return 1;
- return 0;
- }
- int wyznacznik_ppl(int A, int B, int C)
- {
- long long w_ppl = large_lantern[stos[A]].second*large_lantern[stos[B]].first + large_lantern[stos[B]].second*small_lantern[C].first + small_lantern[C].second*large_lantern[stos[A]].first - small_lantern[C].second*large_lantern[stos[B]].first - large_lantern[stos[A]].second*small_lantern[C].first - large_lantern[stos[B]].second*large_lantern[stos[A]].first;
- if (w_ppl >= 0)
- return 1;
- return 0;
- }
- int wyznacznik_ppl2(int A, int B)
- {
- //B = stos[B];
- long long w_ppl2 = small_lantern[A].second*small_lantern[small_lantern.size() - 1].first + small_lantern[small_lantern.size() - 1].second*large_lantern[stos[B]].first + large_lantern[stos[B]].second*small_lantern[A].first - large_lantern[stos[B]].second*small_lantern[small_lantern.size() - 1].first - small_lantern[A].second*large_lantern[stos[B]].first - small_lantern[small_lantern.size() - 1].second*small_lantern[A].first;
- if (w_ppl2 >= 0)
- return 1;
- return 0;
- }
- //wrzucamy do stosu
- void push(int value)
- {
- stos[index++] = value;
- }
- //wyrzucamy ze stosu
- void del()
- {
- index--;
- }
- void graham()
- {
- push(0);
- for (int i = tangens.size() - 1; i >= 0; i--)
- {
- double value = tangens[i].second;
- if (index == 2)
- push(value);
- else
- {
- while (det(stos[index - 2], stos[index - 1], value) == 0 && index != 1)
- del();
- push(value);
- }
- }
- while (det(stos[index - 2], stos[index - 1], 0) == 0 && index != 1)
- del();
- push(0);
- }
- void sort_alpha(int n)
- {
- int large_lantern0_Y = large_lantern[0].first;
- int large_lantern0_X = large_lantern[0].second;
- for (int i = 1; i<n; i++)
- {
- double a = large_lantern[i].second - large_lantern0_X;
- double b = large_lantern[i].first - large_lantern0_Y;
- double tang = a / b * 180 / PI;
- tangens.push_back(make_pair(tang, i));
- }
- sort(tangens.begin(), tangens.end());
- int ind = 1;
- }
- void ppl()
- {
- for (int i = 0; i<small_amount; i++)
- {
- int przeciecia = 0;
- for (int j = 0; j<index - 1; j++)
- {
- if (wyznacznik_ppl(j, j + 1) != wyznacznik_ppl(j, j + 1, i)
- && wyznacznik_ppl2(i, j) != wyznacznik_ppl2(i, j + 1))
- przeciecia++;
- }
- if (przeciecia % 2 != 0)
- {
- ok.push_back(make_pair(small_lantern[i].second, small_lantern[i].first));
- }
- }
- plik << ok.size() << endl;
- }
- void read(string nazwa)
- {
- fstream file;
- file.open(nazwa, ios::in);
- double x, y;
- file >> large_amount;
- for (int i = 0; i<large_amount; i++)
- {
- file >> x;
- file >> y;
- large_lantern.push_back(make_pair(y, x));
- }
- file >> small_amount;
- for (int i = 0; i<small_amount; i++)
- {
- file >> x;
- file >> y;
- small_lantern.push_back(make_pair(y, x));
- }
- small_lantern.push_back(make_pair(pow(2, 30), pow(2, 30)));
- sort(large_lantern.begin(), large_lantern.end());
- sort(small_lantern.begin(), small_lantern.end());
- sort_alpha(large_amount);
- graham();
- ppl();
- }
- int main()
- {
- read("ala.in");
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement