Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <typeinfo>
- #define NMAX 100001
- #define x second
- #define y first
- using namespace std;
- ifstream fin("is.in");
- ofstream fout("is.out");
- typedef pair<int, int>point;
- struct event
- {
- point p1,p2;
- int type;
- event() {};
- event(point p1,point p2, int type) : p1(p1), p2(p2),type(type) {};
- };
- int n,e, nrint;
- event events[NMAX];
- bool compare(event a, event b)
- {
- return a.p1.x<b.p1.x;
- }
- set<point>s;
- void hv_intersection()
- {
- for (int i=0;i<e;++i)
- {
- event c = events[i];
- if (c.type==0)
- s.insert(c.p1);
- else if (c.type==1)
- s.erase(c.p2);
- else
- {
- for (typeof(s.begin()) it=s.lower_bound(make_pair(c.p1.y,-1));it!=s.end() && it->y<=c.p2.y; it++)
- nrint++;
- }
- }
- }
- int main()
- {
- int i;
- fin>>n;
- int p1x,p1y,p2x,p2y;
- for(i=0;i<n;i++)
- {
- fin>>p1x>>p1y>>p2x>>p2y;
- if(p1x==p2x)
- {
- events[e++]=event(make_pair(p1y,p1x),make_pair(p2y,p2x),2);
- }
- else
- {
- events[e++]=event(make_pair(p1y,p1x),make_pair(p2y,p2x),0);
- events[e++]=event(make_pair(p2y,p2x),make_pair(p1y,p1x),1);
- }
- }
- sort(events, events+e,compare);
- hv_intersection();
- fout<<nrint;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement