Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // Created by Acka on 9/22/16.
- //
- #include <stdio.h>
- #include <algorithm>
- using namespace std;
- #define CCW(x1, y1, x2, y2, x3, y3) (x1 * y2 + x2 * y3 + x3 * y1 - x2 * y1 - x3 * y2 - x1 * y3)
- struct Line{ long long int x1, y1, x2, y2;
- void pair_swap(){
- if(x2 < x1){
- swap(x1, x2); swap(y1, y2);
- }
- }
- bool cross(Line &A){
- long long int cross1 = get_op(CCW(x1, y1, x2, y2, A.x1, A.y1)) * get_op(CCW(x1, y1, x2, y2, A.x2, A.y2));
- long long int cross2 = get_op(CCW(A.x1, A.y1, A.x2, A.y2, x1, y1)) * get_op(CCW(A.x1, A.y1, A.x2, A.y2, x2, y2));
- return (cross1 <= 0 && cross2 <= 0);
- }
- int get_op(long long int x){
- return x ? (x < 0 ? -1 : 1) : 0;
- }
- bool operator <(const Line &A)const{
- return x1 == A.x1 ? x2 < A.x2 : x1 < A.x1;
- }
- };
- int main()
- {
- long long int N, ans = 0; scanf("%lld", &N);
- Line l[20000];
- for(int i = 0; i < N; i++){
- scanf("%lld %lld %lld %lld", &l[i].x1, &l[i].y1, &l[i].x2, &l[i].y2);
- l[i].pair_swap();
- }
- sort(l, l + N);
- for(long long int i = 0, miny, maxy; i < N; i++){
- miny = min(l[i].y1, l[i].y2);
- maxy = max(l[i].y1, l[i].y2);
- for(int j = i + 1; j < N; j++){
- if(l[i].x2 < l[j].x1) break;
- if(max(l[j].y1, l[j].y2) < miny || maxy < min(l[j].y1, l[j].y2)) continue;
- if(l[i].cross(l[j])) ans++;
- }
- }
- printf("%lld\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement