Cod sursa(job #950179)

Utilizator enedumitruene dumitru enedumitru Data 16 mai 2013 00:35:04
Problema Rays Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.6 kb
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream f("rays.in"); ofstream g("rays.out");
//struct segment {long long x,y1,y2;};
typedef struct Segment {
    int x, y1, y2;
} Segment;
vector <Segment> v,u;
int n,nr;
//inline int cmp(const segment &a, const segment &b) 
//{	if(a.x*b.y2>b.x*a.y2) return 1; else return 0;}
int cross(int X1, int Y1, int X2, int Y2) {
    long long P = (long long)X1*Y2 - (long long)X2*Y1;
    if (P == 0) return 0;
    return P > 0 ? 1 : -1;
}
 
inline int cmp(Segment a, Segment b) {
    return cross(a.x, a.y2, b.x, b.y2) == 1;
}
int main()
{   f>>n;
	while(n--) 
	{	Segment seg;
		f>>seg.x>>seg.y1>>seg.y2;
		if(seg.y1>seg.y2) swap(seg.y1,seg.y2);
        if(seg.x>0) v.push_back(seg); else {seg.x=-seg.x; u.push_back(seg);}
    }
	sort(v.begin(),v.end(),cmp);
	if(v.size())
    {	++nr;
		for(int i=1; i<v.size(); ++i)
			//if(v[i-1].x*v[i].y1>v[i].x*v[i-1].y2) ++nr;
			if (cross(v[i-1].x, v[i-1].y2, v[i].x, v[i].y1) == 1) nr++;
	}
	sort(u.begin(),u.end(),cmp);
	if(u.size())
    {	++nr;
		for(int i=1; i<u.size(); ++i)
			//if(u[i-1].x*u[i].y1>u[i].x*u[i-1].y2) ++nr;
			if (cross(u[i-1].x, u[i-1].y2, u[i].x, u[i].y1) == 1) nr++;
	}
    g<<nr<<'\n'; g.close(); return 0;
}
/*
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
 
#define pb push_back
#define sz(c) int((c).size())
#define all(c) (c).begin(), (c).end()
 
typedef struct Segment {
    int x, y1, y2;
} Segment;
 
int ret;
vector<Segment> v, u;
 
void ReadData() {
    freopen("rays.in", "r", stdin);
    freopen("rays.out", "w", stdout);
 
    int N;
    for (scanf("%d", &N); N; --N) {
        Segment tmp;
        scanf("%d %d %d", &tmp.x, &tmp.y1, &tmp.y2);
 
        if (tmp.y1 > tmp.y2) tmp.y1 ^= tmp.y2 ^= tmp.y1 ^= tmp.y2;
 
        if (tmp.x > 0) v.pb(tmp);
        else {
            tmp.x *= -1;
            u.pb(tmp);
        }
    }
}
 
int cross(int X1, int Y1, int X2, int Y2) {
    long long P = (long long)X1*Y2 - (long long)X2*Y1;
    if (P == 0) return 0;
    return P > 0 ? 1 : -1;
}
 
inline int cmp(Segment a, Segment b) {
    return cross(a.x, a.y2, b.x, b.y2) == 1;
}
 
void Solve(vector<Segment> &v) {
    sort(all(v), cmp);
    if (!sz(v)) return;
 
    int X = v[0].x;
    int Y = v[0].y2;
    ++ret;
 
    for (int i = 1; i < sz(v); ++i)
        if (cross(X, Y, v[i].x, v[i].y1) == 1) {
            ++ret;
            X = v[i].x;
            Y = v[i].y2;
        }
}
 
int main() {
    ReadData();
    Solve(v);
    Solve(u);
    printf("%d\n", ret);
}
*/