Submission details
Task:Point in Polygon
Sender:aalto26jm_012
Submission time:2026-11-09 17:15:35 +0200
Language:Rust (2021)
Status:READY
Result:
Test results
testverdicttime
#10.01 sdetails
#2ACCEPTED0.01 sdetails
#3ACCEPTED0.00 sdetails
#4ACCEPTED0.00 sdetails
#50.00 sdetails
#60.00 sdetails
#7ACCEPTED0.00 sdetails
#8ACCEPTED0.00 sdetails
#9ACCEPTED0.00 sdetails
#10ACCEPTED0.00 sdetails
#11ACCEPTED0.00 sdetails
#12ACCEPTED0.00 sdetails
#130.00 sdetails
#14ACCEPTED0.01 sdetails

Code

#![allow(unused)]

use std::collections::*;
use std::io;

fn take_tuple() -> (i64, i64) {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let mut it = input
        .trim()
        .split_whitespace()
        .map(|x| x.parse::<i64>().unwrap());
    (it.next().unwrap(), it.next().unwrap())
}

fn point_in_polygon(polygon: &[(i64, i64)], p: (i64, i64)) {
    fn cross(s1: (i64, i64), s2: (i64, i64), p: (i64, i64)) -> i64 {
        (p.0 - s1.0) * (p.1 - s2.1) - (p.0 - s2.0) * (p.1 - s1.1)
    }
    fn on_seg(a: (i64, i64), b: (i64, i64), p: (i64, i64)) -> bool {
        cross(a, b, p) == 0
            && a.0.min(b.0) <= p.0
            && p.0 <= a.0.max(b.0)
            && a.1.min(b.1) <= p.1
            && p.1 <= a.1.max(b.1)
    }
    let n = polygon.len();
    let mut inside = false;
    for i in 0..n {
        let (a, b) = (polygon[i], polygon[(i + 1) % n]);
        if on_seg(a, b, p) {
            println!("BOUNDARY");
            return;
        }

        if (a.1 > p.1 && b.1 < p.1) || (a.1 < p.1 && b.1 > p.1) {
            if (b.1 > a.1 && cross(a, b, p) > 0) || (b.1 < a.1 && cross(a, b, p) < 0) {
                inside = !inside;
            }
        }
    }

    if inside {
        println!("INSIDE");
        return;
    } else {
        println!("OUTSIDE");
        return;
    }
}

fn main() {
    let (n, m) = take_tuple();
    let n = n as usize;
    let m = m as usize;
    let mut ps: Vec<(i64, i64)> = Vec::with_capacity(n);
    for _ in 0..n {
        ps.push(take_tuple());
    }

    for _ in 0..m {
        point_in_polygon(&ps, take_tuple());
    }
}

Test details

Test 1

Verdict:

input
100 1000
-7 -19
91 77
100 100
64 60
...

correct output
INSIDE
OUTSIDE
INSIDE
INSIDE
INSIDE
...

user output
INSIDE
OUTSIDE
INSIDE
INSIDE
INSIDE
...

Feedback: Incorrect character on line 12 col 1: expected "OUTSIDE", got "INSIDE"

Test 2

Verdict: ACCEPTED

input
1000 1000
365625896 -113418831
278762563 38777445
250367343 -96991975
175866909 -129766978
...

correct output
OUTSIDE
OUTSIDE
INSIDE
OUTSIDE
OUTSIDE
...

user output
OUTSIDE
OUTSIDE
INSIDE
OUTSIDE
OUTSIDE
...

Test 3

Verdict: ACCEPTED

input
4 1
1 5
5 5
5 1
1 1
...

correct output
INSIDE

user output
INSIDE

Test 4

Verdict: ACCEPTED

input
4 1
1 5
5 5
5 1
1 1
...

correct output
OUTSIDE

user output
OUTSIDE

Test 5

Verdict:

input
4 1
1 100
2 50
1 20
0 50
...

correct output
INSIDE

user output
OUTSIDE

Feedback: Incorrect character on line 1 col 1: expected "INSIDE", got "OUTSIDE"

Test 6

Verdict:

input
8 1
0 0
0 2
1 1
2 2
...

correct output
INSIDE

user output
OUTSIDE

Feedback: Incorrect character on line 1 col 1: expected "INSIDE", got "OUTSIDE"

Test 7

Verdict: ACCEPTED

input
4 4
0 0
3 0
3 4
0 4
...

correct output
INSIDE
BOUNDARY
OUTSIDE
BOUNDARY

user output
INSIDE
BOUNDARY
OUTSIDE
BOUNDARY

Test 8

Verdict: ACCEPTED

input
6 1
0 0
0 2
3 1
2 2
...

correct output
INSIDE

user output
INSIDE

Test 9

Verdict: ACCEPTED

input
3 1
0 0
1 1000000000
-3 0
1 1

correct output
OUTSIDE

user output
OUTSIDE

Test 10

Verdict: ACCEPTED

input
3 1
-100000 0
-1000000000 -999999999
1000000000 1000000000
0 0

correct output
OUTSIDE

user output
OUTSIDE

Test 11

Verdict: ACCEPTED

input
3 1
-100000 0
-999999999 -1000000000
1000 1000
0 0

correct output
INSIDE

user output
INSIDE

Test 12

Verdict: ACCEPTED

input
4 1
-4 1
-6 1
-6 -1
-4 -1
...

correct output
INSIDE

user output
INSIDE

Test 13

Verdict:

input
3 1
0 10
0 -10
10 0
1 0

correct output
INSIDE

user output
OUTSIDE

Feedback: Incorrect character on line 1 col 1: expected "INSIDE", got "OUTSIDE"

Test 14

Verdict: ACCEPTED

input
3 1000
-536621709 -536621709
955833081 955833081
-1 1
-439278425 -439278425
...

correct output
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
...

user output
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
BOUNDARY
...