SGU192 SGU192： 比较简单的计算几何。给了一些R、G、B三种颜色的线段，然后将线段投影到X轴，问对应颜色的长度。离X轴最近的线段是啥颜色就是啥颜色。 直接离散化，加入端点的X值，以及两两之间交点的X值。 然后枚举每一段，找出每一段的颜色。
192. RGB
time limit per test: 0.25 sec. memory limit per test: 4096 KB
input: standard input output: standard output
There are N segments on a plane (0<N<=300). Each segment is defined by coordinates of the end points (Xi1, Yi1) and (Xi2, Yi2) (i=1,2,…,N). All coordinates are in a range from 0 to 32000. No two segments have more than one common point. Each segment is painted in one of three colors: red (R), green (G), blue (B). All points of all segments are projected to the axis OX (projection is made parallel to the axis OY). Each projected point is painted in color of the point nearest to the axis OX. You have to find the total lengths of the projections painted in red (SR), green (SG) and blue (SB) colors.
Input
The first line contains natural number N. Each of the following N lines contains coordinates of the ends of the segments (4 integer delimited by a space) and the letter (R, G, B), determining the color of a segment.
Output
The first line must contain letter R and number SR delimited by a space. The second line must contain letter G and number SG. The third line must contain letter B and number SB. All numbers should be printed with precision 0.01.
Sample test(s)
Input
4 1 1 3 2 R 2 1 4 2 G 3 1 5 2 B 2 2 3 5 R
Output
R 1 G 1 B 2
计算几何判断线段相交模板，和求直线交点模板搬过来一用，就差不多了。
/* ***
Author :kuangbin
Created Time :2015/1/21 18:18:18
File Name :E:\2014ACM\SGU\SGU192.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include
#include
#include
#include
#include
#include
#include
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const double eps = 1e-8;
int sgn(double x){
if(fabs(x) < eps)return 0;
if(x < 0)return -1;
else return 1;
}
struct Point{
double x,y;
Point(){}
Point(double _x,double _y){
x = _x;
y = _y;
}
void input(){
scanf(“%lf%lf”,&x,&y);
}
Point operator -(const Point &b)const{
return Point(x-b.x,y-b.y);
}
double operator ^(const Point &b)const{
return x*b.y - y*b.x;
}
double operator (const Point &b)const{
return x\b.x + y*b.y;
}
};
struct Line{
Point s,e;
int type;
int get_type(char ch){
if(ch == ‘R’)return 0;
else if(ch == ‘G’)return 1;
else return 2;
}
void input(){
s.input();
e.input();
if(s.x > e.x)swap(s,e);
char ss[3];
scanf(“%s”,ss);
type = get_type(ss[0]);
}
int segcrossseg(Line v){
int d1 = sgn((e-s)^(v.s-s));
int d2 = sgn((e-s)^(v.e-s));
int d3 = sgn((v.e-v.s)^(s-v.s));
int d4 = sgn((v.e-v.s)^(e-v.s));
if( (d1^d2) == -2 && (d3^d4) == -2 )return 2;
return (d1 == 0 && sgn((v.s-s)(v.s-e)) <=0) ||
(d2 == 0 && sgn((v.e-s)(v.e-e)) <= 0) ||
(d3 == 0 && sgn((s-v.s)(s-v.e)) <= 0) ||
(d4 == 0 && sgn((e-v.s)(e-v.e)) <= 0);
}
Point crosspoint(Line v){
double a1 = (v.e-v.s)^(s-v.s);
double a2 = (v.e-v.s)^(e-v.s);
return Point((s.x*a2-e.x*a1)/(a2-a1),(s.y*a2-e.y*a1)/(a2-a1));
}
};
Line line[330];
double x[160000];
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int n;
while(scanf(“%d”,&n) == 1){
int cnt = 0;
for(int i = 0;i < n;i++){
line[i].input();
x[cnt++] = line[i].s.x;
x[cnt++] = line[i].e.x;
}
for(int i = 0;i < n;i++)
for(int j = i+1;j < n;j++)
if(line[i].segcrossseg(line[j]) == 2){
Point tmp = line[i].crosspoint(line[j]);
x[cnt++] = tmp.x;
}
sort(x,x+cnt);
cnt = unique(x,x+cnt)-x;
double ans[3];
ans[0] = ans[1] = ans[2] = 0;
for(int i = 0;i < cnt-1;i++){
if(fabs(x[i+1]-x[i]) < eps)continue;
double xx = (x[i]+x[i+1])/2;
double now;
int tt = -1;
for(int j = 0;j < n;j++){
if(line[j].s.x < xx && xx < line[j].e.x){
double yy = line[j].s.y + (xx-line[j].s.x)*(line[j].e.y-line[j].s.y)/(line[j].e.x-line[j].s.x);
if(tt == -1){
tt = line[j].type;
now = yy;
}
else if(now > yy){
tt = line[j].type;
now = yy;
}
}
}
if(tt != -1){
ans[tt] += x[i+1]-x[i];
}
}
printf(“R %.2lf\n”,ans[0]);
printf(“G %.2lf\n”,ans[1]);
printf(“B %.2lf\n”,ans[2]);
}
return 0;
}
